Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0111 - ROAD TRIP

   You are planning a road trip to visit your friends, each of whom live in different towns. Of course, you don't want to pay any more for fuel on the trip than you need to. However, the price of fuel in each of the towns is different, so you will need to carefully plan the trip to minimise the cost. For example, it might make sense to take on extra fuel at a town where the price is low so that you don't need to buy so much at a town where it is more expensive. Indeed, it may even make sense to sell excess fuel at some towns to recoup some of the costs. Of course, your car can only hold a certain amount of fuel, and you have to make sure you take on enough fuel at each town to reach the next (assume that it's OK to arrive with an empty tank).

   Your task is to write a program to help you plan your trip.

Input

   Input will consist of specifications for a series of journeys. Information for each journey will begin with a line containing an integer 0 < c < 100 that specifies the capacity of the car's fuel tank in litres and an integer 0 < t < 20 that specifies the number of towns to visit for that journey. A line containing two zeros indicates the end of input.

   The following t lines contain information about successive stages on the journey: the price (in fixed point dollars-and-cents format, 0.01 <= p < 9.99) of one litre of fuel (either to buy or to sell) in the town at the beginning of the stage, and the number of litres of fuel (an integer, 1  <= n < 100) needed to reach the next town.

Output

   Output should consist of one line for each journey comprising the journey number (formatted as shown) followed by a single space and the minimum cost of completing that journey, formatted as a fixed-point number with 2 decimal places.

Examples

stdin

stdout

1

10 3

2.00 7

1.50 8

1.00 3

50 6

1.50 20

4.20 5

1.15 35

1.41 27

1.92 30

2.21 15

0 0

Journey 1: 29.00

Journey 2: 117.64


Ավելացրեց.Հրանտ Հովհաննիսյան (ԳՏՏԿ)
Ամսաթիվ.2014-01-30
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Australian Programming Contest 2013.G

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.