← 返回题目列表

AtCoder · agc073_d

D. 四颗宝石

中文机器翻译题面 查看原题

分数: 1700 点

问题陈述

这个世界上,有 K 宝石类型编号为 1 to K(=4)。 该类型宝石每单位尺寸的价值 i is W_i.

Snuke 有 N 宝石。 的 i-th gem 的类型 A_i 并且有尺寸 B_i。 另外,斯努克还有 N 框,其中 i第一个盒子有尺寸 i.

Snuke 现在会在每个盒子里放一颗宝石。 当宝石的尺寸大于盒子时,宝石会被切割以适合盒子。 也就是说,当宝石 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