题目描述

一场活动持续 $n$ 天，服务站从 $1$ 开始编号。第 $i$ 天，只有编号为 $1,2,\ldots,c_i$ 的服务站开放；若 $c_i=0$，则当天没有服务站开放。每个开放的服务站每天必须恰好安排一个小组值班，未开放的服务站不能安排值班。

共有 $m$ 个候选小组，你可以从中选用若干个。第 $j$ 个小组一旦被选用，就必须在同一个服务站连续值班恰好 $d_j$ 天，产生的总收益为 $v_j$。每个小组最多使用一次，值班日期必须全部位于活动的 $n$ 天内。

在满足所有值班要求的前提下，求最大总收益。若不存在可行安排，输出 $0$；若所有服务站始终关闭，总收益也为 $0$。

输入格式

第一行包含两个整数 $n,m$，表示活动天数和候选小组数。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，描述每天开放的服务站。

接下来 $m$ 行，第 $j$ 行包含两个整数 $d_j,v_j$，表示第 $j$ 个小组的连续值班天数和总收益。

输出格式

输出一行一个整数，表示最大总收益；不存在可行安排时，输出 $0$。

样例输入 1

3 4
2 1 2
3 4
1 2
1 5
1 7

样例输出 1

16

样例 1 解释

让第 $1$ 个小组在 $1$ 号站连续值班 $3$ 天；第 $3$、$4$ 个小组分别在第 $1$、$3$ 天到 $2$ 号站值班。总收益为 $4+5+7=16$，这是最大值。

样例输入 2

2 1
1 1
1 8

样例输出 2

0

样例 2 解释

唯一的小组只能值班 $1$ 天，无法覆盖 $1$ 号站连续开放的两天，因此不存在可行安排，输出 $0$。

数据范围与子任务

对于所有测试数据，保证$1\le n\le10^5$，$1\le m\le16$，$0\le c_i\le10^5$，$1\le d_j\le n$，$0\le v_j\le10^6$。

每个子任务内的正式测试全部通过，才获得该子任务的分数。