Arad loves eating sushi, but only after 4:00 PM, when it is cheaper. However, a certain capybara knows this and wants to steal Arad's sushi.

Each day, Arad buys sushi at exactly one of ~n~ possible times: ~0, 1, \dots, n-1~ minutes after 4:00 PM. The capybara knows the probability distribution of the time at which Arad buys sushi.

The capybara can stand outside the sushi shop for one contiguous window of time. If it waits for ~k~ minutes starting at minute ~s~, it will catch Arad if he buys sushi at any of the minutes ~s, s+1, \dots, s+k-1~.

The capybara wants at least an ~m~ percent chance of stealing Arad's sushi. Since it is very lazy, find the minimum number of minutes it must wait.

Input

The first line contains two integers ~n~ and ~m~ (~1 \leq n \leq 10^5~, ~1 \leq m \leq 100~): the number of possible purchase times and the required percentage chance of success.

The second line contains ~n~ integers ~x_0, x_1, \dots, x_{n-1}~ (~0 \leq x_i \leq 10^5~), where ~x_i~ is the probability weight for minute ~i~. At least one weight is positive.

The probability that Arad buys sushi at minute ~i~ is

$$\displaystyle \frac{x_i}{x_0+x_1+\dots+x_{n-1}}. $$

Output

Output a single integer: the minimum number of minutes the capybara must stand outside the sushi shop to have at least an ~m~ percent chance of stealing Arad's sushi.

Examples

Input 1

10 50
1 2 3 2 3 5 7 9 2 2

Output 1

3

The capybara can wait for ~3~ minutes starting at 4:05 PM. The probability of success is ~\frac{21}{36}~, which is at least ~50\%~.

Input 2

10 100
1 2 3 2 3 5 7 9 2 2

Output 2

10

Since every possible purchase time has positive weight, the capybara must wait for all ~10~ minutes to guarantee a ~100\%~ chance of stealing the sushi.