The great kidnapping

After the voting in the previous exercises, the attackers were able to successfully kidnap the most clever member of each team. Following this, they used military-grade mind altering techniques on the remaining members, so that they completely forget that this +1 person even existed. The goal of the attackers is to create a super clever team from the kidnapped people and reach world dominance! Luckily when the system administrators used backups to restore every data from the previous cyber attacks they noticed some logs which proved that each team had one extra members. However we have no information regarding where this extra person is and how long will they stay there. But luckily during the escape, one of the attackers left a note which lets you calculate how many days you have until the memory altering techniques can completely overwrite your kidnapped teammates' mind and make them "one of the criminals".

Input

The input consists of two lines, each closed by an end of line character.

• The first line contains two positive integers n and m, separated by a single space character. The number n denotes the amount of money the attackers have to lodge the kidnapped people and the number m tells us how many days they need to completely mind-wipe them.
• The second line contains at most 100 positive integers, separated by a single space character. These numbers are the prices of rooms at different hotels (the kidnappers do not like to stay at the same place for too long).

Output

The output is a single positive integer based on the following:

• If in the second line of the input (in the prices of hotel rooms) there is at least one m-long, consecutive subsequence such that its sum is less or equal than n, then print out the sum of the subsequence which is the "cheapest".
• If there are no subsequences like this, then print out the length of the longest consecutive subsequence which has a total sum less or equal than n.

Note: for this exercise you may get a "partially correct" answer if your code gives the expected output for at least 50% of the test cases.

Example

Explanation

In the first case we are searching for a 2-long consecutive subsequence, since the attackers want to hide for 2 days only. The consecutive subsequences are the following: [3,7], [7,6], [6,3]. The first and last are okay in terms of the available money (which is 10), but the cheapest possibility is the [6,3], which requires 9 money. So we return 9.
In the second case the available money is 50 and they want to lodge for 3 days, so we are searching for 3 long consecutive subsequences, which are: [10,40,5], [40,5,8], [5,8,47]. However each of them has a sum greater than 50, so it is impossible for them to lodge for 3 days. However since e.g. [10,40] or [40,5] or [5,8], etc. are in their budget, then they can lodge for up to 2 days, so in this case we return the maximum amount of days which is 2.