You have ~N~ balls and ~M~ colours. Each ball will have a specific colour and a specific value. You are only allowed to take ~K~ balls of each colour. Given ~Q~ queries of ~K~, What is the maximum total value that you can achieve?

Input Specification

The first line will contain ~N~ ~(1 \leq N \leq 10^5)~, ~M~ ~(1 \leq M \leq 10^5)~ and ~Q~ ~(1 \leq Q \leq 10^5)~, the number of balls, number of colours and the number of queries, respectively. The next ~N~ lines will each contain a string ~s~ ~1 \leq |S| \leq 100)~ and integer ~a_i~ ~(1 \leq a_i \leq 10^9)~, the colour and value of the ball. The string will only contain capital and lowercase letters. The next ~Q~ lines will each contain one integer ~K~ ~(0 \leq K \leq N)~, the maximum number of balls you can pick from each colour.

Subtask 1 [30%]

~N \leq 1000, M \leq 1000, Q \leq 1000~

Subtask 2 [70%]

No further constraints.

Output Specification

For each query, print the maximum total value that you can achieve by taking at most ~K~ balls from each colour.

Note that you may have to use long for this problem.

Sample Input 1

6 3 2
Red 5
Green 2
Red 8
Blue 4
Blue 0
Green 3
1
2

Sample Output 1

15
22

Sample Explanation 1

By taking ~1~ of each ball, we can get a total value of ~8+3+4=15~. For ~2~ of each ball, we take all of them to get a total value of ~22~.