Gimli's Gullet

Interview

Time limit1sMemory limit256 MB

Summary

Pack unlimited servings of M foods into capacity C for the most calories, breaking ties by the lexicographically smallest serving counts.

Level: Medium5 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Legolas and Gimli are packing rations before they leave the Woodland Realm, and the kitchen has badly underestimated the belly of a dwarf. Gimli refuses to take a step until his pack holds as many calories as it can.

The kitchen has $M$ kinds of food. Each kind has a volume per serving and a calorie count per serving. Gimli can order any number of servings of a kind, including none. Choose how many servings of each food to order so that the total volume fits in the space left in the pack and the total calorie count is as large as possible.

Several orders can reach the same largest calorie count. In that case the answer is the one whose sequence of quantities comes first in lexicographic order: order as few servings as possible of the first food, then, under that condition, as few servings as possible of the second food, and so on.

Input

The input holds several test cases. The first line of a test case has one integer $C$ , the space left in Gimli's pack in cubic centimeters. The second line has one integer $M$ , the number of foods on offer. Each of the next $M$ lines has two integers, the volume $v_i$ of one serving in cubic centimeters and its calorie count $c_i$ . These lines are given in non-decreasing order of volume.

A test case whose first line is 0 marks the end of the input, and it produces no output.

$1 \le C \le 10000$ , $1 \le M \le 20$ , $1 \le v_i \le 10000$ , $0 \le c_i \le 100000$ , and $v_1 \le v_2 \le \dots \le v_M$ . At most 10 test cases come before the terminating 0.

Output

For each test case, print one line with $M$ integers separated by single spaces. The $i$ -th integer is the number of servings of the $i$ -th food that Gimli should order.

When several orders reach the largest calorie count, print the sequence of quantities that comes first in lexicographic order.

Examples6

Example 1

Input

Expected output

0 2 11 0
76 0

Example 2
Input
```
5
3
10 100
20 250
30 400
0
```
Expected output
```
0 0 0
```
Example 3
Input
```
100
1
100 7
0
```
Expected output
```
1
```
Example 4
Input
```
10
2
3 5
3 5
0
```
Expected output
```
0 3
```
Example 5
Input
```
7
2
3 4
5 7
0
```
Expected output
```
2 0
```
Example 6
Input
```
9
3
1 0
2 3
4 5
0
```
Expected output
```
0 4 0
```