AT_abc261_d [ABC261D] Flipping and Bonus

高桥君要进行 $N$ 次抛硬币。他还持有一个计数器，初始时计数器的数值为 $0$。 在第 $i$ 次抛硬币时，根据正反面的结果，会发生以下情况： - 如果是正面：高桥君将计数器的数值加 $1$，并获得 $X_i$ 日元。 - 如果是反面：高桥君将计数器的数值重置为 $0$，且无法获得金钱。 此外，有 $M$ 种连续奖励，第 $i$ 种连续奖励为：每当计数器的数值变为 $C_i$ 时，可以获得 $Y_i$ 日元。 请你求出高桥君最多可以获得多少日元。

输入以如下格式从标准输入给出。 > $N$ $M$ $X_1$ $X_2$ $\ldots$ $X_N$ $C_1$ $Y_1$ $C_2$ $Y_2$ $\vdots$ $C_M$ $Y_M$

请输出高桥君能够获得的最大金额（整数）。

### 限制条件 - $1\leq M\leq N\leq 5000$ - $1\leq X_i\leq 10^9$ - $1\leq C_i\leq N$ - $1\leq Y_i\leq 10^9$ - $C_1,C_2,\ldots,C_M$ 均互不相同。 - 输入均为整数。 ### 样例解释 1 依次出现正面、正面、反面、正面、正面、正面时，获得的金额如下： - 第 $1$ 次抛硬币为正面。计数器从 $0$ 变为 $1$，获得 $2$ 日元。 - 第 $2$ 次抛硬币为正面。计数器从 $1$ 变为 $2$，获得 $7$ 日元，并作为连续奖励获得 $10$ 日元。 - 第 $3$ 次抛硬币为反面。计数器从 $2$ 变为 $0$。 - 第 $4$ 次抛硬币为正面。计数器从 $0$ 变为 $1$，获得 $8$ 日元。 - 第 $5$ 次抛硬币为正面。计数器从 $1$ 变为 $2$，获得 $2$ 日元，并作为连续奖励获得 $10$ 日元。 - 第 $6$ 次抛硬币为正面。计数器从 $2$ 变为 $3$，获得 $8$ 日元，并作为连续奖励获得 $1$ 日元。 此时高桥君共获得 $2+(7+10)+0+8+(2+10)+(8+1)=48$ 日元，为最大值。 请注意，连续奖励每当计数器数值变为 $C_i$ 时都可以获得多次。 顺便一提，若 $6$ 次抛硬币全部为正面，则只能获得 $2+(7+10)+(1+1)+8+(2+5)+8=44$ 日元，不是最大值。 ### 样例解释 2 请注意，答案可能超出 $32$ 位整数范围。 由 ChatGPT 4.1 翻译