已结束 GESP挑战赛#8

A3119 | 投硬币

时间限制2s
内存限制256MB
通过 / 提交0/0

题目描述

时间限制:2000ms

内存限制:256MB


小码君接下来会投掷硬币 $N$ 次。他还有一个计数器,初始值为 0。

根据第 $i$ 次掷硬币的结果:

- 如果是正面:将计数器的值增加 $1$,并获得 $X_i$ 元。
- 如果是反面:将计数器的值重置为 $0$,并且不会得到钱。

另外,还有 $M$ 种额外奖金。
第 $i$ 种奖金会在计数器的值为 $C_i$ 时,每次奖励 $Y_i$ 元。

求小码君能获得的最大金额。

$\large{数据范围}$

- $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$ 互不相等。
- 所有输入数值均为整数。

输入格式

对于每个测试文件格式如下:
$\tt{N\ M}$

$\tt{X_1\ X_2\ \ldots\ X_N}$
$\tt{C_1\ Y_1}$
$\tt{C_2\ Y_2}$
$\tt{\vdots}$
$\tt{C_M\ Y_M}$

输出格式

对于每个测试文件输出小码君能够获得的最大金额。

输入输出样例

输入 #1
6 3
2 7 1 8 2 8
2 10
3 1
5 5
输出 #1
48
输入 #2
3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000
输出 #2
5000000000
C++ 编辑器
输入
输出