김리의 식량 배낭

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

주방에는 $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$ 번째 음식을 주문해야 하는 개수이다.

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