当前没有测试数据。

D - 翻转和奖励

分数: $400$ 分

题目描述

Takahashi 要投掷一枚硬币 $N$ 次。 他还有一个计数器，开始时显示为 $0$。

根据第 $i$ 次硬币投掷的结果，会发生以下情况:

• 如果是正面: Takahashi 将计数器的值增加 $1$，并获得 $X_i$ 日元（日本货币）。
• 如果是反面: 他将计数器的值重置为 $0$，不获得任何钱。

此外，有 $M$ 种连续奖励。第 $i$ 种连续奖励每次计数器显示 $C_i$ 时奖励 $Y_i$ 日元。

求 Takahashi 可以获得的最大金额。

约束

• $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$ 两两不同。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出:

$N$ $M$

$X_1$ $X_2$ $\ldots$ $X_N$

$C_1$ $Y_1$

$C_2$ $Y_2$

$\vdots$

$C_M$ $Y_M$

输出

输出 Takahashi 可以获得的最大金额，作为一个整数。

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

48

如果顺序为 head, head, tail, head, head, head，Takahashi 会获得以下金额。

• 第一次硬币投掷是正面。计数器的值从 $0$ 变为 $1$，并获得 $2$ 日元。
• 第二次硬币投掷是正面。计数器的值从 $1$ 变为 $2$，并获得 $7$ 日元。另外，获得 $10$ 日元作为连续奖励。
• 第三次硬币投掷是反面。计数器的值从 $2$ 变为 $0$。
• 第四次硬币投掷是正面。计数器的值从 $0$ 变为 $1$，并获得 $8$ 日元。
• 第五次硬币投掷是正面。计数器的值从 $1$ 变为 $2$，并获得 $2$ 日元。另外，获得 $10$ 日元作为连续奖励。
• 第六次硬币投掷是正面。计数器的值从 $2$ 变为 $3$，并获得 $8$ 日元。另外，获得 $1$ 日元作为连续奖励。

此时，Takahashi 总共获得了 $2+(7+10)+0+8+(2+10)+(8+1)=48$ 日元，这是可能的最大金额。
注意，计数器显示 $C_i$ 时每次都有可能获得连续奖励。
另外，值得一提的是，如果他在所有 $6$ 次硬币投掷中都获得了正面，他只能获得 $2+(7+10)+(1+1)+8+(2+5)+8=44$ 日元，这不是最大值。

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

5000000000

请注意，答案可能不适合 $32$ 位整数类型。