묵직한 동전 문제

당신은 동전으로 물건값을 치르기를 좋아하지만 문제가 하나 있습니다. 잔돈이 너무 많아 주머니가 무거워졌습니다. 이 무게를 줄일 계획을 세웠고, 그 계획을 실행할 프로그램이 필요합니다.

다음에 살 물건의 값은 $C$센트입니다. 가진 동전 중 일부를 골라 총액이 $C$ 이상이 되도록 지불하며, 더 많이 내면 가게가 거스름돈을 돌려줍니다. 지불이 끝난 뒤 주머니에 남는 동전들 — 즉 지불하지 않은 동전과 가게가 거슬러 준 동전 — 의 총 무게가 가장 작아지도록 어떤 동전을 낼지 고르세요.

가게가 당신에게 $X$센트를 거슬러 줘야 할 때는 탐욕적으로 거스름돈을 만듭니다. 값이 $X$ 이하인 액면 중 가장 큰 동전 하나를 주고 그 값만큼 $X$에서 빼며, $X$가 $0$이 될 때까지 이를 반복합니다. 가게는 모든 액면의 동전을 무제한으로 가지고 있습니다.

액면은 $D$가지입니다. $i$번째 액면은 정수 값 $V_i$(센트)와 무게 $W_i$(그램)를 가집니다. 정확히 한 액면의 값이 $1$이며, 값이 같은 액면은 없습니다.

당신은 $K$개의 동전을 가지고 있고, $j$번째 동전의 액면은 $D_j$입니다.

제약: $1 \le C \le 100000$, $1 \le D \le 100$, $1 \le K \le 100$, $1 \le V_i \le 2000$, $0 < W_i < 10$(소수 둘째 자리까지 주어짐), $1 \le D_j \le D$.

첫 줄에 정수 세 개 $C$, $D$, $K$가 주어집니다. 각각 물건값(센트), 동전 액면의 수, 당신이 가진 동전의 수입니다.

다음 $D$개의 줄에는 정수 $V_i$와 (정확히 소수 둘째 자리까지 주어지는) 실수 $W_i$가 주어집니다. 각각 $i$번째 액면의 값(센트)과 무게(그램)입니다.

다음 $K$개의 줄에는 정수 $D_j$가 하나씩 주어집니다. $j$번째 동전의 액면 번호(1부터 시작)입니다.

물건을 살 수 있다면 달성 가능한 최소 총 무게를 그램 단위로 소수 둘째 자리까지 반올림하여 출력합니다(답은 항상 $0.01$의 정확한 배수입니다). 살 수 없다면 too poor를 출력합니다.

5센트 동전 일곱 개를 가지고 3센트짜리 물건을 산다고 합시다. 액면은 1, 5, 10, 20센트이며 무게는 각각 1, 2, 1, 9그램입니다.

한 가지 최적해는 5센트 동전 세 개를 내는 것입니다. 그러면 가게가 12센트를 거슬러 주며 10센트 하나와 1센트 둘을 돌려줍니다. 다른 최적해는 5센트 동전 네 개를 내는 것으로, 가게가 17센트를 거슬러 주며 10센트 하나, 5센트 하나, 1센트 둘을 돌려줍니다. 두 경우 모두 주머니에 $11.00$그램이 남습니다.