A Musical Question

면접 대비

시간 제한11초메모리 제한1024 MB

요약

같은 용량의 CD 두 장에 노래를 나누어 담아 총 재생 시간을 최대로 하고, 동점이면 두 CD의 시간 차가 가장 작은 답을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

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 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 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.

예제2

예제 1
입력
```
100 5
10 20 40 60 85
```
예상 출력
```
100 95
```
예제 2
입력
```
100 5
10 20 30 40 50
```
예상 출력
```
80 70
```