题目描述

黄老师的生日马上要到了，徐老师想给他买一些礼物

众所周知，直男买礼物只会买大玩偶

徐老师有 $n$ 张面值分别为 $a_1,a_2,a_3...a_n$ 的纸币

而礼品店里有 $m$ 种玩偶，每种玩偶有它的价格 $w_i$ 和体积 $v_i$，当然每种玩偶的库存是无限的

徐老师对钱没有多少概念，但是他有很奇特的花钱习惯：

1. 徐老师很懒，不想算钱，所以他不会把几张纸币凑在一起去买玩偶
2. 一张纸币的面值如果和玩偶价格相等，徐老师是不会买的
3. 一张纸币只用一次，找回来的钱是不会继续花的

徐老师想知道他最终能买到的玩偶体积总和最大是多少。

输入格式

第一行两个整数 $n$，$m$ 代表徐老师有的纸币的张数和玩偶种类

第二行 $n$ 个整数代表每张纸币的面值 $a_1,a_2...a_n$

接下来 $m$ 行每行两个整数 $w_i$，$v_i$ 代表第 $i$ 种玩偶的价格和体积

输出格式

输出一个整数，代表 徐老师能买到的最大体积总和。

数据范围

对于 $30\%$ 的数据：$Nn = 1$ , $m = 1$ , $1 \le a_i, w_i , v_i \le 100$ 。

对于 $60\%$ 的数据：$1 \le n \times m \le 1000000$, $1 \le a_i, w_i, v_i \le 100$ , 保证所有的价值 $v_i$ 都相等。

对于 $100\%$ 的数据：$1 \le n \times m \le 1000000$, $1 \le a_i, w_i, v_i \le 100$。

样例输入

2 2
2 3
1 2
2 3

样例输出

5