#1433. [L2-2] 音游

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luoshuitianyi

题目描述

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

这款音游的计分规则也很独特,它有 “基础得分”:对于第 个“音符”,若小 “成功判定”,则将会获得 分;若 “失败判定”,不得分。

但同时,它还有 条 “特殊规则”,其中第 条 “特殊规则” 是:对于每一段的 “连续成功判定”,若它的长度至少,则小 将会获得 的额外分数(对于 ,不一定有 ,即不同的 “特殊规则” 可能会要求相同的 )。

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

输入格式

第一行两个正整数

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

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

输出格式

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

样例

样例输入

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

样例输出

48

样例解释

对于第 个 “音符”,它们 “成功判定”;对于第 个 “音符”,它 “失败判定”。

“基础得分” 为:;因为有一个长度 的、一个长度为 的 “连续成功判定”,触发了两次 的 “特殊规则”,一次 的 “特殊规则”,所以 “特殊规则” 得分为 ;总得分:

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

数据范围与提示

对于前 的数据,

对于另外 的数据,

对于另外 的数据,

对于所有数据,