Hide

Problem C
Songbook

Languages en sv

Doris will be the toastmaster at a dinner with her university chapter. During the evening, they will of course be singing songs! As Doris is quite uninformed of the songs in their songbook, she has choosen to instead pick as many songs as possible during the $t$ minutes allocated for singing. As she is otherwise busy with picking who will speak and what they should say, she has asked for your help in this endeavor.

Input

Begins with a row containing two integers, the number of minutes allocated for singing, $t < 10^5$, and the number of songs in their songbook. Then follows one row with $n$ integers, the expected seconds to sing each song, $s_ i < t \cdot 60$.

Output

One row with a single integer, the minimal number of seconds it takes to sing the most amount of songs possible.

Points

Your solution will be tested on a number of testgroups. To earn points in a testgroup all tests in it must succeed.

Group

Points

Limits

$1$

$20$

All songs take the same time to sing.

$2$

$40$

$n \leq 16$

$3$

$40$

No further restrictions

Sample Input 1 Sample Output 1
4 4
110 110 110 110
220
Sample Input 2 Sample Output 2
1 2
30 20
50
Sample Input 3 Sample Output 3
2 5
60 120 250 299 1
61

Please log in to submit a solution to this problem

Log in