Drink Responsibly

Time limit1sMemory limit256 MB

Summary

Decide whether whole numbers of up to eight drinks can total exactly m in cost and u in alcohol, and print the lexicographically smallest purchase.

Level: Medium6 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

The University of Lagado runs a beer tasting during Fresher's week. For safety the university caps how much money one student may spend, and each student sets a personal limit on the alcohol they will drink that night.

Drinks are served in one of three sizes: a litre, half a litre, or a third of a litre. One unit of alcohol is the amount contained in one litre of a drink of strength 1 percent. A drink of strength $s$ percent served in a size of $f$ litres therefore holds $s \times f$ units.

A student wants to spend all $m$ of their money, down to the last coin, and drink exactly $u$ units of alcohol. No more and no less. Any drink may be bought any number of times, including none. Decide whether such a purchase exists, and if it does, print what to buy and how many of each.

Input

The first line holds three values.

$m$ ( $0.01 \le m \le 10.00$ ), the money available, written to two decimal places.
$u$ ( $0.0 \le u \le 20.0$ ), the number of units aimed for, written to one decimal place.
$d$ ( $1 \le d \le 8$ ), the number of different drinks on sale.

Each of the next $d$ lines holds four values separated by single spaces.

The name of the drink, up to 20 lowercase latin letters. The $d$ names are distinct.
Its strength, an integer percentage between 0 and 100.
Its size, 1/1 for a litre, 1/2 for half a litre, 1/3 for a third of a litre.
Its cost, a real number between 0.00 and 10.00 written to two decimal places.

Output

If no purchase spends exactly $m$ and delivers exactly $u$ units, print one line holding IMPOSSIBLE.

Otherwise print one line for every drink bought, in the order the drinks appear in the input, giving the name and then the number bought, separated by one space. A drink bought zero times is not printed.

Several purchases may work. Write $c_i$ for the number bought of the $i$ -th drink of the input, so that a purchase is the sequence $(c_1, c_2, \dots, c_d)$ , and print the purchase that comes first in lexicographic order: take the smallest $c_1$ , among those the smallest $c_2$ , and so on to the end.

Because $m$ is at least 0.01, any purchase that exists buys at least one drink, so the output is never empty.

Examples8

Example 1

Input

10.00 9.0 2
fire 2 1/1 4.00
water 10 1/2 2.00

Expected output

fire 2
water 1

Example 2

Input

2.00 3.0 3
firewater 1 1/1 1.00
windwater 1 1/1 1.00
earthwater 1 1/1 1.00

Expected output

IMPOSSIBLE

Example 3
Input
```
1.00 2.0 1
cider 3 1/3 0.50
```
Expected output
```
cider 2
```
Example 4
Input
```
3.00 0.0 1
juice 0 1/1 1.50
```
Expected output
```
juice 2
```

Example 5

Input

4.00 4.0 2
alpha 1 1/1 1.00
beta 2 1/1 2.00

Expected output

beta 2

Example 6

Input

1.00 3.0 2
gratis 1 1/1 0.00
tonic 0 1/1 1.00

Expected output

gratis 3
tonic 1

Example 7

Input

10.00 20.0 1
vodka 40 1/2 5.00

Expected output

IMPOSSIBLE

Example 8
Input
```
0.50 0.0 1
ale 5 1/2 0.50
```
Expected output
```
IMPOSSIBLE
```