分数: 400 点
问题陈述
高桥会抛硬币 N 次。 他还有一个计数器,最初显示 0.
取决于结果 i第 次抛硬币,会发生以下情况:
- 如果正面:高桥将计数器的值增加 1 并接收 X_i 日元(日本货币)。
- 如果它尾随:他将计数器的值重置为 0,没有收到钱。
此外,还有 M 各种连胜奖金。的 i-第一种连胜奖励 Y_i 日元 每次 计数器显示 C_i.
求高桥能收到的最大金额。
约束
- 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
输出
以整数形式打印高桥可以收到的最大金额。
示例输入 1
6 3 2 7 1 8 2 8 2 10 3 1 5 5
示例输出 1
48
如果他按顺序得到头、头、尾、头、头、头,则奖励以下金额。
- 在 1-st 抛硬币,硬币正面。更改计数器的值 0 to 1 并接收 2 日元。
- 在 2-nd 抛硬币,硬币正面。更改计数器的值 1 to 2 并接收 7 日元。另外,得到 10 日元作为连续奖金。
- 在 3-rd 抛硬币,硬币反面。更改计数器的值 2 to 0.
- 在 4第 次抛硬币,硬币正面朝上。更改计数器的值 0 to 1 并接收 8 日元。
- 在 5第 次抛硬币,硬币正面朝上。更改计数器的值 1 to 2 并接收 2 日元。另外,得到 10 日元作为连续奖金。
- 在 6第 次抛硬币,硬币正面朝上。更改计数器的值 2 to 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
3 2 1000000000 1000000000 1000000000 1 1000000000 3 1000000000
示例输出 2
5000000000
请注意,答案可能不适合 32位整数类型。