Score : 400 points
You have N cards. On the i-th card, an integer A_i is written.
For each j = 1, 2, ..., M in this order, you will perform the following operation once:
Operation: Choose at most B_j cards (possibly zero). Replace the integer written on each chosen card with C_j.
Find the maximum possible sum of the integers written on the N cards after the M operations.
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N B_1 C_1 B_2 C_2 \vdots B_M C_M
Print the maximum possible sum of the integers written on the N cards after the M operations.
3 2 5 1 4 2 3 1 5
14
By replacing the integer on the second card with 5, the sum of the integers written on the three cards becomes 5 + 5 + 4 = 14, which is the maximum result.
10 3 1 8 5 7 100 4 52 33 13 5 3 10 4 30 1 4
338
3 2 100 100 100 3 99 3 99
300
11 3 1 1 1 1 1 1 1 1 1 1 1 3 1000000000 4 1000000000 3 1000000000
10000000001
The output may not fit into a 32-bit integer type.