B. Инфляция
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть статистика роста цен некоторого товара в виде массива из $$$n$$$ положительных целых чисел $$$p_0, p_1, \dots, p_{n - 1}$$$, где $$$p_0$$$ — это начальная цена товара, а $$$p_i$$$ — это насколько подорожал товар за $$$i$$$-й месяц.

Используя эти данные вам нужно посчитать коэффициенты инфляции для каждого месяца как отношение текущего подорожания $$$p_i$$$ к цене товара на начало месяца $$$(p_0 + p_1 + \dots + p_{i - 1})$$$.

Ваш босс вам ясно дал понять, что коэффициенты инфляции не должны превышать $$$k$$$ %, поэтому вы решили увеличить некоторые значения $$$p_i$$$ таким образом, что все $$$p_i$$$ — все еще целые числа, а коэффициенты инфляции за каждый месяц не будут превосходить $$$k$$$ %.

Вы знаете, что чем сильнее изменения — тем очевиднее обман. А потому вам нужно минимизировать сумму изменений.

Какую наименьшую сумму изменений вам нужно сделать, чтобы все коэффициенты инфляции не превосходили $$$k$$$ %?

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 100$$$; $$$1 \le k \le 100$$$) — длина массива $$$p$$$ и коэффициент $$$k$$$.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$p_0, p_1, \dots, p_{n - 1}$$$ ($$$1 \le p_i \le 10^9$$$) — массив $$$p$$$.

Выходные данные

Для каждого набора входных данных выведите наименьшую сумму изменений, которые сделают все коэффициенты инфляции не превосходящими $$$k$$$ %.

Пример
Входные данные
2
4 1
20100 1 202 202
3 100
1 1 1
Выходные данные
99
0
Примечание

В первом наборе входных данных, вы можете, например, увеличить $$$p_0$$$ на $$$50$$$ и $$$p_1$$$ на $$$49$$$ и получить массив $$$[20150, 50, 202, 202]$$$. Тогда у вас получатся следующие коэффициенты инфляции:

  1. $$$\frac{50}{20150} \le \frac{1}{100}$$$;
  2. $$$\frac{202}{20150 + 50} \le \frac{1}{100}$$$;
  3. $$$\frac{202}{20200 + 202} \le \frac{1}{100}$$$;

Во втором наборе, вам не нужно модифицировать массив $$$p$$$, так как все коэффициенты инфляции уже подходят:

  1. $$$\frac{1}{1} \le \frac{100}{100}$$$;
  2. $$$\frac{1}{1 + 1} \le \frac{100}{100}$$$;