Варка овощей

Хитрость варки овощей состоит в том, чтобы все кусочки были примерно одинакового размера. Если они не являются таковыми, то маленькие кусочки получаются слишком мягкими, а крупные недоваренными. К счастью, Вы слышали о кухонном ноже, хотя предупреждения Ваших родителей об использовании острых инструментов до сих пор находятся в Вашей голове. Поэтому Вы хотите использовать его как можно меньше. Вы можете взять кусок овоща весом $w$ и разрезать его произвольным образом на две части с весами $w_{left}$ и $w_{right}$, где $w_{left}+w_{right}=w$. Эту операцию назовем "разрез".

Зная размеры имеющихся кусков овощей, определить наименьшее количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше заданного порогового значения.

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

Начинается с действительного числа $t(0.5<t<1)$ с $2$ десятичными цифрами и натурального числа $n(n\le 1000)$. Далее идут $n$ целых положительных весов $w_1,w_2,...,w_n$. Все веса меньше чем $10^6$.

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

Вывести минимальное количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше $t$. Считайте, что число необходимых разрезов меньше $500$. Чтобы избежать проблем с действительными числами, предположим, что оптимальный ответ для отношения $t$ будет таким же, как и для отношения $t+0.0001$.

Примеры