← 返回题目列表

AtCoder · abc261_d

G. 翻转和奖金

中文机器翻译题面 查看原题

分数: 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位整数类型。