2009 Canadian Computing Competition, Stage 2

Day 2, Problem 3: A Weighty Problem

You like to make purchases using coins, but you have a problem: you have so much change that it is too heavy in your pocket. You have devised a plan to reduce the weight of your change, and you need to write a program to help you execute it.

Here is your plan. The next purchase you make costs C (1 ≤ C ≤ 100,000) cents, and you know how the store will pay back change if you pay extra. You want to select some of your coins that have total value at least C and make the purchase, such that you minimize the weight of the coins you did not spend added to the weight of the coins the store returns to you.

If the store owes you X cents, then it uses the following algorithm to pay you back. The store gives you the largest denomination coin that has value at most X, and repeats this until all X cents have been paid to you. You may assume the store has an unlimited amount of every denomination of coin.

There are D (1 ≤ D ≤ 100) denominations of coins. The i'th denomination (1 ≤ i ≤ D) has integer value V_i (1 ≤ V_i ≤ 2000) in cents and real-valued weight W_i (0 < W_i < 10) in grams. You may assume that one of the denominations has value 1 and that no two denominations have the same value.

You have K (1 ≤ K ≤ 100) coins. The j'th coin (1 ≤ j ≤ K) is of the denomination with index D_j (1 ≤ D_j ≤ D).

In 20% of test cases, K ≤ 10.

Input

The first line contains three integers: C, the cost of the purchase in cents; D, the number of denominations of coins; and K, the number of coins you have.

The next D lines contain an integer V_i, the value of the i'th denomination in cents, and a real number given to two decimal places, Wi, the weight of the i'th denomination in grams.

The next K lines contain an integer D_j , the 1-based denomination of the j'th coin you have.

Output

Output the minimum weight achievable rounded to two decimal places, if you can afford the purchase. If you cannot afford the purchase, print too poor. (no period)

Sample Input

3 4 7
1 1.00
5 2.00
20 9.00
10 1.00
2
2
2
2
2
2
2

Sample Output

11.00

Explanation

You have seven 5-cent coins, and are making a purchase of 3 cents. The denominations are 1-cent, 5-cents, 10-cents, and 20-cents, with respective weights of 1 gram, 2 grams, 1 gram and 9 grams.

There are two optimal solutions. One is to spend three 5-cent coins, so that the store returns 12 cents to you, in the form of one 10-cent coin and two 1-cent coins. The other is to spend four 5-cent coins, so that the store returns 17 cents to you, in the form of one 10-cent coin, one 5-cent coin, and two 1-cent coins.

All Submissions
Best Solutions

Point Value: 20
Time Limit: 1.00s
Memory Limit: 128M
Added: Jun 06, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Better make sure two decimal places are displaced since the judge asks for exactly two.

Do the 7 2s mean that you have 7 of the coins that have weight 2.00 or 7 of the second coin in the list of coins?

The explanation makes this clear.