Варіння овочів

Хитрість у приготуванні овочів полягає в тому, щоб усі шматочки були приблизно однакового розміру. Якщо вони такими не є, то маленькі шматочки можуть переваритися, а великі залишитися сирими. На щастя, ви знаєте про кухонний ніж, хоча застереження ваших батьків щодо використання гострих інструментів досі у вас в голові. Тому ви хочете використовувати ніж якомога менше. Ви можете взяти шматок овоча вагою $w$ і розрізати його на дві частини з вагами $w_{left}$ і $w_{right}$, де $w_{left}+w_{right}=w$. Цю операцію назвемо "розріз".

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

Вхідні дані

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

Вихідні дані

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

Приклади