AT_agc073_d [AGC073D] Four Jewels

In this world, there are $ K $ types of gems numbered from $ 1 $ to $ K(=4) $ . The value per unit size of a gem of type $ i $ is $ W_i $ . Snuke has $ N $ gems. The $ i $ -th gem is of type $ A_i $ and has size $ B_i $ . Also, Snuke has $ N $ boxes, where the $ i $ -th box has size $ i $ . Snuke will now put one gem in each box. When a gem's size is larger than the box, the gem is cut to fit in the box. That is, when gem $ i $ is put in box $ j $ , its value becomes $ W_{A_i} \times \min(B_i, j) $ . Find the maximum possible sum of gem values.

The input is given from Standard Input in the following format: > $ N $ $ K $ $ W_1 $ $ W_2 $ $ \ldots $ $ W_K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

Output the answer.

### Sample Explanation 1 If gems $ 1, 2, 3 $ are put in boxes $ 3, 1, 2 $ , respectively, the sum of values is $ 4 \times \min(2, 3) + 1 \times \min(3, 1) + 3 \times \min(2, 2) = 15 $ , which is maximum. ### Constraints - $ K = 4 $ - $ 1 \leq W_1 < W_2 < \cdots < W_K \leq 10^6 $ - $ 1 \leq N \leq 250000 $ - $ 1 \leq A_i \leq K $ - $ 1 \leq B_i \leq N $ - All input values are integers.