Şehmettin is a well-known entrepreneur. In his shop, he displays \(\mathbf{N}\) Pokemon card packs in a row. On each pack, there is a label displaying the number of cards included in it.

Şehmettin decided to give a special offer. The special offer states that, if someone finds the largest possible sequence of card packs that satisfy the given constraints they can then get those packs for free! But if they can't they will pay the price for those packs without getting anything.

Rules for choosing card packs are:

• The card packs must be chosen in an ordered fashion, going from left to right.
• Card packs must be chosen in non-decreasing order of the number of cards inside them.
• In the selection, the same labeled packs can be chosen up to \(\mathbf{K}\) number of times.

Based on these rules, find the number of card packs included in the largest sequence of card packs, in order to get them for FREEEEEEE!!!

Input

The first line contains 2 integers \(\mathbf{N}\) and \(\mathbf{K}\). The total number of card packs and the maximum number of same numbered card packs you can choose.

• \(1\leq\mathbf{N}\leq1000\).
• \(1\leq\mathbf{K}\leq N\)

The second line contains \(\mathbf{N}\) integers. The number \(\mathbf{a_i}\) is the number of cards in the \(i^{th}\) card pack.

• \(1\leq\mathbf{a_i}\leq1000\)

Output

Print the largest possible number of card packs that satisfy the given constraints to get them for free.

Example

Input 1:

10 3
3 1 3 1 1 3 2 3 3 3

Output 1:

7

Input 2:

16 3
3 4 5 4 2 1 1 4 3 1 5 4 1 4 1 2

Output 2:

5

Explanation

Input 1

The best combination is 1 1 1 2 3 3 3. You would get 7 card packs using this combination.

Note that another combination to get 7 card packs is 1 1 1 3 3 3 3. However, this combination is invalid, because the number of 3's in this combination is \(4\) which is greater than \(\mathbf{K}=3\).

Input 2

The best combinations are 3 4 4 4 5, 1 1 3 4 4, 1 1 4 4 4, and 1 1 1 4 4. You would get 5 card packs using these combinations.