AT_agc073_d [AGC073D] Four Jewels

在这个世界上，有 $K$ 种宝石，编号从 $1$ 到 $K$（$K=4$）。第 $i$ 种宝石的单位体积价值为 $W_i$。 Snuke 有 $N$ 颗宝石。第 $i$ 颗宝石为 $A_i$ 类型，体积为 $B_i$。此外，Snuke 还有 $N$ 个箱子，第 $i$ 个箱子的大小为 $i$。 Snuke 现要把每颗宝石分别放入每个箱子中。若宝石体积大于箱子体积，宝石会被切割以适应箱子。也就是说，当第 $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$

输出答案。

### 样例解释 1 如果将第 $1,2,3$ 颗宝石分别放入第 $3,1,2$ 号箱子，则总价值为 $4 \times \min(2,3) + 1 \times \min(3,1) + 3 \times \min(2,2) = 15$，这是可能获得的最大值。 ### 数据范围 - $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$ - 所有输入数值均为整数。 由 ChatGPT 5 翻译