#1433. [L2-2] 音游

小 $x$ 正在玩一款音游。这款音游有 $n$ 个 “音符” 按照一定的顺序依次出现。对于每一个 “音符”，小 $x$ 对它进行 “判定”，结果要么是 “成功判定”，要么是 “失败判定”。我们称一段连续的 “判定” 是 “连续成功判定” 的，当且仅当这段连续的 “音符” 起始于 “失败判定” 的后一个 “音符”，或者起始于第一个 “音符”；终止于 “失败判定” 的前一个 “音符”，或者终止于最后一个 “音符”；并且在这个连续的 “音符” 中没有 “失败判定”。

这款音游的计分规则也很独特，它有 “基础得分”：对于第 $i$ 个“音符”，若小 $x$ “成功判定”，则将会获得 $a_i$ 分；若 “失败判定”，不得分。

但同时，它还有 $m$ 条 “特殊规则”，其中第 $j$ 条 “特殊规则” 是：对于每一段的 “连续成功判定”，若它的长度至少为 $l_j$，则小 $x$ 将会获得 $v_j$ 的额外分数（对于 $\forall j_1\not= j_2$，不一定有 $l_{j_1}\not= l_{j_2}$，即不同的 “特殊规则” 可能会要求相同的 $l_j$）。

显然由于特殊规则的存在，Full Combo（所有 “音符” 均为 “成功判定”）不一定会为你带来最高的分数。所以小 $x$ 想问你他最多能获得多少分。

第一行两个正整数 $n,m$ 。

接下来一行 $n$ 个正整数 $a_i$，表示 $n$ 个 “音符” 按照一定的顺序出现，它们所对应的 “基础得分”。

接下来 $m$ 行每行两个正整数 $l_j, v_j$，表示特殊规则：对于每一段的 “连续成功判定”，若 “连续成功判定” 的长度至少为 $l_j$，则将会获得 $v_j$ 的额外分数。

一行一个正整数代表答案，即最多能获得的分数。

样例输入

6 3
2 7 1 8 2 8
2 10
3 1
5 5

样例输出

48

样例解释

对于第 $1,2,4,5,6$ 个 “音符”，它们 “成功判定”；对于第 $3$ 个 “音符”，它 “失败判定”。

“基础得分” 为：$2+7+8+2+8=27$；因为有一个长度 $2$ 的、一个长度为 $3$ 的 “连续成功判定”，触发了两次 $l_j=2$ 的 “特殊规则”，一次 $l_j=3$ 的 “特殊规则”，所以 “特殊规则” 得分为 $10+10+1=21$；总得分：$27+21=48$。

可以证明，这样得分是最高的。

对于前 $30\%$ 的数据，$n\le15$ 。

对于另外 $20\%$ 的数据，$l_j=1$ 。

对于另外 $30\%$ 的数据，$a_i=0$ 。

对于所有数据，$1\le m\le n\le 5000,0\le a_i,v_i\le 10^9,1\le l_i\le n$ 。