分数: 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