Money Money Money, Must Be Funny

• Shopkeeper: "That will be 100 crowns and 80 hellers, please."
• Customer: "Here you are." (handing over a 200-crown banknote)
• Shopkeeper: "Would you have 80 hellers?" (passing back a 100-crown note)
• Customer: "No, but here you are." (adding a 1-crown coin)
• Shopkeeper: "Sorry, I only have this." (showing a shiny 50-heller coin)
• Customer: "Then I still owe you 30 hellers, but I only have 40."
• Shopkeeper: "That's fine — here are the remaining 10."

Have you ever been in a situation like this? Paying an exact amount can be surprisingly hard when the coins and banknotes ("tenders") you carry are limited. In the end the exchange above worked out: the customer paid 200 + 1 crowns, received 100 + 0.50 back, then paid another 0.20 + 0.20, and finally received 0.10 back — so 7 tenders changed hands in total. Sometimes it gets even more complicated.

One crown is worth 100 hellers, so every amount can be written with at most two decimal places. Your task is to write a program that, given what the customer and the shopkeeper each carry, finds the smallest number of tenders that must change hands to settle a given amount. The customer hands over some of their tenders and the shopkeeper returns some of theirs as change; a tender counts as "exchanged" whether it is paid or returned.

The input describes several tasks.

Each task begins with a line holding one non-negative number: the amount to be paid. Next comes the list of tenders the customer (the one who pays) carries. Every line of the list holds the tender's nominal value (a non-negative number), a single space, the number of tenders of that value (a non-negative integer), and the lowercase letter x — for example, 200 3x means three tenders worth 200. The list ends with a line containing -1.

After the customer's list comes the shopkeeper's list (the one who receives the payment), in exactly the same format and also ended by -1. Then the next task begins. After the last task, one more line containing -1 marks the end of the input.

Each list holds at most 100 lines. No one carries more than 10,000 units in total, nor more than 500 individual tenders. Nominal values need not follow any real-world currency. Every value that may be non-integer is given either as an integer or as a decimal number with one or two digits after the decimal point.

For each task, print one line: X tenders must be exchanged., where X is the smallest number of tenders that must change hands to pay the required amount exactly. If the amount cannot be paid at all, print The payment is impossible. instead.