김리의 식량 배낭

면접 대비

시간 제한1초메모리 제한256 MB

요약

용량 C 배낭에 M가지 음식을 원하는 만큼 담아 열량을 최대화하고 동점이면 사전 순으로 가장 앞선 수량을 출력합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법
정답자: 아직 제출이 없습니다

문제

레골라스와 김리가 어둠숲 왕국을 떠나기 전에 식량을 챙기고 있다. 그런데 주방이 준비한 양은 드워프의 식성에 한참 못 미친다. 김리는 배낭이 담을 수 있는 열량을 최대로 채우기 전에는 한 발짝도 움직이지 않겠다고 버틴다.

주방에는 $M$ 가지 음식이 있고, 음식마다 한 개의 부피와 열량이 정해져 있다. 같은 음식을 원하는 개수만큼 주문할 수 있고, 하나도 주문하지 않아도 된다. 주문한 음식의 부피 합이 배낭에 남은 공간을 넘지 않으면서 열량 합이 최대가 되도록 각 음식의 개수를 정하자.

열량 합이 최대인 주문이 여러 가지면, 개수를 앞에서부터 늘어놓은 수열이 사전순으로 가장 앞서는 것을 답으로 한다. 첫 번째 음식의 개수를 될 수 있는 대로 적게 하고, 그 조건에서 두 번째 음식의 개수를 될 수 있는 대로 적게 하는 식으로 정하면 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 배낭에 남은 공간 $C$ 가 세제곱센티미터 단위의 정수로 주어진다. 둘째 줄에는 음식의 종류 수 $M$ 이 주어진다. 이어지는 $M$ 개의 줄에는 음식 한 개의 부피 $v_i$ (세제곱센티미터)와 열량 $c_i$ 가 공백을 사이에 두고 주어진다. 이 줄들은 부피가 감소하지 않는 순서로 주어진다.

남은 공간이 0인 테스트 케이스는 입력의 끝을 뜻하며, 이 케이스는 처리하지 않는다.

$1 \le C \le 10000$ , $1 \le M \le 20$ , $1 \le v_i \le 10000$ , $0 \le c_i \le 100000$ , $v_1 \le v_2 \le \dots \le v_M$ 이다. 처리해야 하는 테스트 케이스는 10개 이하이다.

출력

각 테스트 케이스마다 한 줄에 $M$ 개의 정수를 공백 하나로 구분해 출력한다. $i$ 번째 정수는 김리가 $i$ 번째 음식을 주문해야 하는 개수이다.

열량 합이 최대인 주문이 여러 가지면, 개수 수열이 사전순으로 가장 앞서는 것을 출력한다.

예제6

예제 1

입력

예상 출력

0 2 11 0
76 0

예제 2
입력
```
5
3
10 100
20 250
30 400
0
```
예상 출력
```
0 0 0
```
예제 3
입력
```
100
1
100 7
0
```
예상 출력
```
1
```
예제 4
입력
```
10
2
3 5
3 5
0
```
예상 출력
```
0 3
```
예제 5
입력
```
7
2
3 4
5 7
0
```
예상 출력
```
2 0
```
예제 6
입력
```
9
3
1 0
2 3
4 5
0
```
예상 출력
```
0 4 0
```