警察局位于珠宝店巷的最顶端，这对镇上的扒手生意至关重要。警察每天从巷子顶端开始巡逻，缓慢向下行进，然后再返回顶端，在白天很少到达巷子的底端。警察的习惯有很多规律，因此扒手大老板（BPB）可以为假期制定一个精明的计划。巷子里的商店从底端到顶端依次用整数编号，从 1 开始。在假期的每一天，BPB 都可以保证从起点到某个特定编号的商店是安全的，不会受到警察的干扰。扒手团队将为 BPB 执行任务。现有许多团队，每个团队都可以在一家商店工作若干个连续的天数。不一定要雇佣所有团队。

BPB 是一位令人生畏的老板，他的规则必须严格遵守：

• 在任何商店安全的当天，该商店内必须恰好有一个团队在工作。
• 当一个团队开始在某家商店工作时，他们将在那里工作若干个连续的天数。
• 当某家商店在某一天不安全时，当天没有任何团队会在该商店工作。
• 没有团队会在两家或更多的商店工作。
• 没有团队会在假期期间工作两次或以上。
• 没有团队会在假期之前或之后的任何一天工作。

已知每个团队在整个工作期间都能为 BPB 产生特定的最低收入。BPB 知道他必须最大化他的最低总收入。他希望你在今天下午 3 点之前得到这个数字，不得延误。千万不要试图让他失望。

输入格式

第一行包含两个整数 $H$ 和 $T$ ($1 \le H \le 10^5, 1 \le T \le 16$)，分别表示假期天数和可用团队数量。 第二行包含 $H$ 个整数 $C_k$ ($0 \le C_k \le 10^5, 1 \le k \le H$)，表示假期第 $k$ 天安全商店的最高编号。编号 0 表示假期第 $k$ 天没有安全的商店。 接下来的 $T$ 行，每行包含两个整数 $D_t$ 和 $I_t$ ($1 \le D_t \le H, 0 \le I_t \le 10^6, 1 \le t \le T$)，分别表示团队 $t$ 的工作天数和该团队产生的最低收入。

输出格式

输出在合理安排下，团队所能产生的最低总收入的最大值。如果无法满足 BPB 的条件，则输出 0。

样例

输入 1

3 4
2 1 2
3 2
1 1
1 2
1 3

输出 1

7

输入 2

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

输出 2

11