In order to improve the landscape architecture and environmental situation, the municipal administration has developed a draft program for greening the central avenue. According to the project, on one side of the avenue, it is planned to plant trees of K different species in a row, for which tree seedlings were purchased, and a
i seedlings were purchased.
To achieve the aesthetic perfection of the planted row of trees, it is required that among any P consecutive trees, all trees be of different species. If the number of trees in a row is less than P, then they must all be different.
It is required to write a program that finds the maximum number of trees in an aesthetically perfect row planted from purchased seedlings.
Input
The first line contains two integers: K — number of different tree species (1 ≤ K ≤ 100,000), and P — the required number of consecutive trees of different species (2 ≤ P ≤ K). The next K lines of input data contain integers ai, specifying the number of purchased tree seedlings of the i-th type (1 ≤ a
i ≤ 10
9), by one number per line.
Imprint
Print a single number — the maximum number of trees that, planted in a row in some order, achieves aesthetic perfection.
Examples
| # |
Input |
Output |
| 1 |
3 3
1
200
1 |
4 |