Pumps and Pipes

For centuries fire departments have fought fires with water. Unfortunately there is not always enough water right where a fire is burning, so fire departments carry many pumps and pipes to move water to where it is needed. Building the line of pumps and pipes is not trivial, because several physical limits must be respected.

Only one kind of pipe is used: each pipe has a diameter of 75 millimeters and a length of 20 meters. Depending on the flow of water pushed through the pipes, pressure is lost along the way. The pressure loss per meter depends on the flow $f$ (in liters per minute) as follows:

Pressure is also affected by the slope of the land: it changes by 1 bar for every 10 meters of vertical distance — decreasing where a pipe runs uphill and increasing where it runs downhill.

A pump needs an input pressure of at least 2 bar and produces a constant output pressure of 8 bar, but a pump can never be used to lower the pressure. A pipe cannot withstand a pressure above 12 bar, and to keep a steady flow the pressure must be at least 2 bar at every point. At the end of the line the pressure must be at least 5 bar and at most 8 bar for effective fire fighting.

There is always a pump at the very beginning of the line (position 0). Additional pumps may be placed only where two pipes meet, and never at the end of the line.

Write a program that finds the smallest number of pumps needed together with their positions. If several placements use the same smallest number of pumps, choose the one that keeps the pumps closest to the beginning of the line (carrying pumps far is no fun).

The first line contains the number of scenarios.

Each scenario begins with a single integer $f \in {200, 400, 600, 800, 1000, 1200}$ on a line by itself, the desired flow in liters per minute. The next line contains two integers $n$ and $m$ separated by a single space, where $1 \le n \le 20$ is the number of pipes to be used and $1 \le m \le 400$ is the number of segments of constant slope.

The following $m$ lines each describe one segment with two integers $l$ and $s$ separated by a single space: $l > 0$ is the length of the segment in meters and $s$ is its slope in percent ($s = 10$ means the pipe rises 10 meters over a length of 100 meters, $s = -50$ means it drops 50 meters over 100 meters; $-100 \le s \le 100$).

The $m$ segment lengths are guaranteed to add up to exactly $n \times 20$ meters.

For each scenario, first print a line Scenario #i:, where $i$ is the scenario number starting at 1.

On the next line, if a valid placement exists, print the number of pumps (including the pump at the start), then a colon and a single space : , then the pump positions separated by commas with no spaces. A pump position is a pipe-junction index: index 0 is the start of the line and index $j$ is the point right after the first $j$ pipes. Among all placements that use the fewest pumps, print the one whose positions are lexicographically smallest (make the first pump position as small as possible, then the next, and so on). If no placement satisfies all the conditions, print no solution instead.

Separate consecutive scenarios with a single blank line.