Problem E
A Musical Question
Bob Roberts likes to listen to music while he drives, but the car he owns is a little antiquated. No Bluetooth or USB connections here, but at least he has a CD player, so he’s been transferring a lot of his music to CDs. At the moment he has only two CDs left and would like to get as much of his remaining music as possible on them. Given the capacity of the CDs and collection of songs, can you help him find the maximum number of minutes of music he can put on the two CDs?
Input
Input starts with a line containing two integers $c$ $n$, where $c$ $(1 \leq c\leq 1\, 000)$ is the number of minutes of music each CD can hold, and $n$ $(1 \leq n \leq 1\, 000)$ is the number of songs to select from. Following this is a single line containing $n$ positive integers indicating the length (in minutes) of each of the songs. No song will be longer than $1\, 000$ minutes.
Output
Output the amount of music on each CD, in minutes, that maximizes the total amount of music that Bob can transfer to the two CDs. Display the time of the larger-filled CD first. If there is a tie, use the solution which minimizes the time difference between the two CDs.
| Sample Input 1 | Sample Output 1 |
|---|---|
100 5 10 20 40 60 85 |
100 95 |
| Sample Input 2 | Sample Output 2 |
|---|---|
100 5 10 20 30 40 50 |
80 70 |
