该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

连胜奖章

题目描述

学校游园会设置了一项投币挑战。一场挑战需要将一枚硬币投掷 $N$ 次，开始时总分为 $0$，连续正面次数也为 $0$。

第 $i$ 次投掷对应一个分值 $X_i$，根据硬币结果执行以下操作：

• 如果是正面，连续正面次数增加 $1$，总分增加 $X_i$。
• 如果是反面，连续正面次数变为 $0$，总分扣除 $X_i$。

此外还有 $M$ 条连胜奖励。第 $j$ 条奖励由两个整数 $C_j,Y_j$ 表示：每次投掷后，如果连续正面次数恰好为 $C_j$，总分额外增加 $Y_j$。各条奖励的 $C_j$ 互不相同。同一条奖励可以在一场挑战中获得多次。

总分在挑战过程中允许为负数。请在所有可能的正反面结果序列中，求完成全部 $N$ 次投掷后能够得到的最大总分。

输入格式

第一行包含两个整数 $N,M$。

第二行包含 $N$ 个整数 $X_1,X_2,\ldots,X_N$。

接下来 $M$ 行，每行包含两个整数 $C_j,Y_j$，表示一条连胜奖励。

数据范围：

• $1\le M\le N\le 5000$；
• $1\le X_i\le 10^9$；
• $1\le C_j\le N$；
• $1\le Y_j\le 10^9$；
• 所有 $C_j$ 互不相同；
• 输入中的所有数均为整数。

输出格式

输出一个整数，表示最大总分。

输入输出样例

输入 #1

3 1
1 1 1
1 10

输出 #1

21

输入 #2

4 2
1000000000 1000000000 1000000000 1000000000
2 1000000000
4 1000000000

输出 #2

6000000000

样例解释

样例 1

选择“正面、反面、正面”，三次得分分别为 $1+10=11$、$-1$、$1+10=11$，总分为 $21$。反面既会扣分，也会让下一次正面重新触发连续一次的奖励。

样例 2

四次都为正面时，基础得分共 $4\times10^9$，连续两次和连续四次的奖励各获得一次，总分为 $6\times10^9$。