Вы получили работу в игровой студии, которая разработала и поддерживает онлайн шутер, и ваша первая по-настоящему большая работа — это помочь в балансировке оружия. В игре есть \(n\) пушек: у \(i\)-й пушки есть целочисленная скорость стрельбы \(f_i\) и целочисленный урон от одного выстрела \(d_i\). Таким образом, общая огневая мощь \(i\)-й пушки равна \(p_i = f_i \cdot d_i\).
Для начала, вам дали задачу изменить значения \(d_i\) некоторых пушек таким образом, чтобы новые значения \(d_i\) оставались целыми и огневая мощь всего оружия оказалась сбалансирована. Вам дали число \(k\), и сказали, что оружие сбалансировано, если \(\max\limits_{1 \le i \le n}{p_i} - \min\limits_{1 \le i \le n}{p_i} \le k\).
Так как игроки не любят больших изменений, вам нужно изменить значения \(d_i\) у наименьшего возможного количества пушек. Чему равно наименьшее количество пушек, у которых вы должны изменить урон, чтобы сделать игру сбалансированной?
Заметьте, что новые значения \(d_i\) должны быть целыми и строго больше \(0\).
Выходные данные
Для каждого набора входных данных, выведите наименьшее количество пушек, у которых нужно изменить урон \(d_i\), чтобы сделать все оружие сбалансированным.
Заметим, что новые значения \(d_i\) должны быть целыми и больше \(0\).
Примечание
В первом наборе входных данных вы можете выставить \(d_1 = 2\) и \(d_2 = 4\). Вы получите массив \(d = [2, 4, 1, 2]\) и общую огневую мощь \(p = [12, 12, 13, 14]\). Пушки сбалансированы, так как \(14 - 12 \le 2\).
Во втором наборе вы должны изменить урон \(d_i\) всех трех пушек. Например, вы можете сделать \(d = [5151, 5100, 5050]\).
В третьем наборе все оружие уже сбалансировано, и вам не нужно ничего менять.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 2
6 3 13 7
1 2 1 2
3 2
100 101 102
100 99 98
5 0
1 12 4 4 3
12 1 3 3 4
2 50
1000 10
1000000000 1
3 5
1 19 11
49 4 72
|
2
3
0
1
2
|