AT_agc073_d [AGC073D] Four Jewels

この世界には $ 1 $ から $ K(=4) $ までの番号がついた $ K $ 種類の宝石があります． 種類 $ i $ の宝石の大きさ $ 1 $ あたりの価値は $ W_i $ です． すぬけくんは $ N $ 個の宝石を持っています． $ i $ 番目の宝石は種類 $ A_i $ で，大きさ $ B_i $ です． また，すぬけくんは $ N $ 個の箱を持っており， $ i $ 番目の箱は大きさ $ i $ です． すぬけくんは今から，それぞれの箱に宝石を $ 1 $ つずつ入れます． 宝石の大きさが箱より大きいときは，箱に入るように宝石を削ります． つまり，宝石 $ i $ を箱 $ j $ に入れると，その価値は $ W_{A_i} \times \min(B_i,j) $ になります． 宝石の価値の総和としてありうる最大値を求めてください．

入力は以下の形式で標準入力から与えられる． > $ N $ $ K $ $ W_1 $ $ W_2 $ $ \ldots $ $ W_K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

答えを出力せよ．

### Sample Explanation 1 宝石 $ 1,2,3 $ をそれぞれ箱 $ 3,1,2 $ に入れると，価値の総和は $ 4 \times \min(2,3)+1 \times \min(3,1)+3 \times \min(2,2)=15 $ となり，これが最大です． ### 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 $ - 入力はすべて整数である