抛硬币奖励 - 代码源竞赛平台

题目描述

蜗蜗要连续抛 $N$ 次硬币，并记录一个初始为 $0$ 的计数器。第 $i$ 次抛掷若为正面，计数器加 $1$，同时得到 $X_i$ 元；若为反面，计数器立即归零，也得不到钱。

另外有 $M$ 种连续正面奖励。第 $j$ 种奖励规定：每当计数器变为 $C_j$，蜗蜗就额外得到 $Y_j$ 元。同一种奖励在计数器归零后仍可再次获得。

蜗蜗可以选择每次抛掷的结果。求他最多能得到多少钱。

输入格式

第一行包含两个整数 $N,M$，分别表示抛掷次数和奖励种数。

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

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

输出格式

输出一行一个整数，表示能够得到的最大金额。

样例

3 2
1 2 3
1 4
2 5

15

2 1
10 20
2 100

130

样例解释

样例 1 中，三次都选择正面，得到 $1+2+3$ 元；计数器先后达到 $1$ 和 $2$，再得到 $4+5$ 元，总计 $15$ 元。

样例 2 中，两次都选择正面，得到 $10+20+100=130$ 元。

数据范围

对于 100% 的数据，保证 $1\le M\le N\le 5000$，$1\le X_i,Y_j\le 10^9$，$1\le C_j\le N$，且所有 $C_j$ 互不相同。