Problem G
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 |
