Road Trip

You are planning a road trip to visit friends who live in different towns. You do not want to spend more on fuel than you have to, but every town sells fuel at its own price, so the trip needs careful planning. Taking on extra fuel where it is cheap means buying less where it is expensive, and at some towns selling surplus fuel back is the better move. The tank holds only so much, and at every town you must take on enough fuel to reach the next one. Arriving with an empty tank is fine.

Write a program that plans the trip.

The input describes a series of journeys. Each journey begins with a line holding the capacity of the fuel tank $c$ in litres ($0 < c < 100$) and the number of towns to visit $t$ ($0 < t < 20$). A line containing two zeros ends the input.

The next $t$ lines describe the successive stages of that journey. Each line holds the price $p$ of one litre of fuel in the town at the start of the stage, written in fixed point dollars and cents with $0.01 \le p < 9.99$, and the number of litres $n$ needed to reach the next town, an integer with $1 \le n < 100$. Buying and selling use the same price.

Every stage is reachable, so $n$ never exceeds $c$.

Print one line per journey. Write the journey number in the form Journey k:, then a single space, then the minimum cost of completing that journey as a fixed point number with two decimal places. Here $k$ is the journey number, counting from 1.