E. Casino II
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Casino I and II are two different problems, but you should read Casino I in order to understand the statement.

Oussama got angry because the mega millions jackpot was just a big box of candies. Taking revenge, he decided to break the dealer's system. Oussama got the leak and realized that the reals given by the dealer are hard-coded on a big array $$$A$$$.

In fact, starting from $$$i\leftarrow 0$$$ before the first game, each random number is generated by the dealer as follow:

  1. generate $$$A_i$$$ as the random number.
  2. increment $$$i:\quad i\leftarrow i+1$$$

Oussama got the array and now knows the sequence of numbers that will get generated. He was wondering how many rounds he can win at most while knowing the values of the array if he plays exactly $$$k$$$ rounds.

Note that in each game, you cannot skip your first move : you should take at least one card.

Oussama is busy eating candies. Please help him !

Input

You will be given an integer $$$n$$$ ($$$10 \le n \le 10000$$$) : The length of the array and $$$k$$$ ($$$1 \le k \le 1000$$$) : The number of rounds you have to play.

Then you will be given $$$n$$$ reals between $$$0$$$ and $$$1$$$. Note that the reals are randomly and uniformly generated.

Output

Output $$$m$$$ : The maximum number of rounds you can win out of $$$k$$$ rounds.

Examples
Input
10 2
0.43436 0.14373 0.60797 0.02197 0.76351 0.52623 0.41605 0.08398 0.75709 0.67884
Output
0
Input
10 2
0.34985 0.81288 0.34235 0.54262 0.49512 0.62882 0.60371 0.26639 0.29891 0.42121
Output
1
Note
  • For each test case, the index $$$i$$$ will not be reset after each game, It will in fact increment indefinitely.
  • It is guaranteed that the hard-coded array is sufficient to play $$$k$$$ rounds regardless of the strategy of playing.