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

输入 #1

6 3
2 7 1 8 2 8
2 10
3 1
5 5

输出 #1

48

输入输出样例 #2

输入 #2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

输出 #2

5000000000

说明/提示

限制条件

• $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 翻译