D - Four Jewels Editorial /

Time Limit: 15 sec / Memory Limit: 1024 MiB

配点 : 1700 点

問題文

この世界には 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) になります．

宝石の価値の総和としてありうる最大値を求めてください．

制約

  • 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
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

N K
W_1 W_2 \ldots W_K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを出力せよ．

入力例 1

3 4
1 2 3 4
4 2
1 3
3 2

出力例 1

15

宝石 1,2,3 をそれぞれ箱 3,1,2 に入れると，価値の総和は 4 \times \min(2,3)+1 \times \min(3,1)+3 \times \min(2,2)=15 となり，これが最大です．

入力例 2

3 4
1 2 3 4
3 1
2 2
1 3

出力例 2

10

入力例 3

6 4
1 3 8 10
2 2
1 4
2 2
3 1
3 4
4 3

出力例 3

86

入力例 4

15 4
239277 249169 419371 744281
2 14
1 4
1 11
4 12
1 7
2 12
3 15
2 5
3 4
1 8
3 2
4 1
1 15
3 5
2 8

出力例 4

39858078

Score : 1700 points

Problem Statement

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.

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.

Input

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

Output the answer.

Sample Input 1

3 4
1 2 3 4
4 2
1 3
3 2

Sample Output 1

15

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.

Sample Input 2

3 4
1 2 3 4
3 1
2 2
1 3

Sample Output 2

10

Sample Input 3

6 4
1 3 8 10
2 2
1 4
2 2
3 1
3 4
4 3

Sample Output 3

86

Sample Input 4

15 4
239277 249169 419371 744281
2 14
1 4
1 11
4 12
1 7
2 12
3 15
2 5
3 4
1 8
3 2
4 1
1 15
3 5
2 8

Sample Output 4

39858078