徐老师喜欢旅游，但是他手机不太好，掉电很快。 有一次去旅游，他的——手机电量为 0%，四下也找不到插座。好在他习惯性带了几块不同型号的充电宝。 每种型号的充电宝“每 1% 电量”都能支撑手机运行一段固定时长；把一块用干，就换下一块接着用（不使用时不会漏电）。

已知：

• 有 $n$ 种型号，第 $i$ 种的“每 1% 电量”可支撑 $x_i$ 秒；
• 一共有 $m$ 块充电宝，按使用顺序编号为 $1\ldots m$；第 $i$ 块的型号为 $t_i$，剩余电量为 $a_i$。

请你帮徐老师算一算：把这些充电宝按顺序全部用掉，手机还能坚持多少秒？

输入格式

• 第一行：两个正整数 $n, m$。
• 第二行：$n$ 个正整数，依次为 $x_1, x_2, \ldots, x_n$。
• 接下来 $m$ 行：第 $i$ 行给出两个正整数 $t_i, a_i$，表示第 $i$ 块充电宝的型号与剩余电量百分比。

说明：使用顺序固定为输入给定的次序；同型号不同电量的充电宝视为不同个体。

输出格式

• 输出一行一个整数：手机还能继续使用的总秒数。

样例

3 4
200 300 400
1 50
2 100
3 10
2 20

50000

样例解释

• 第 1 块：型号 1，$50$ 电 → $200\times 50=10000$ 秒
• 第 2 块：型号 2，$100$ 电 → $300\times 100=30000$ 秒
• 第 3 块：型号 3，$10$ 电 → $400\times 10=4000$ 秒
• 第 4 块：型号 2，$20$ 电 → $300\times 20=6000$ 秒 合计 $10000+30000+4000+6000=50000$ 秒。

数据范围

• 对于 $30$ 的数据：$n=m=1$；
• 对于 $60$ 的数据：$n=1$；
• 对于 $100$ 的数据： $ n \le 500,\quad m \le 10000,\quad 1 \le x_i \le 600,\quad 1 \le t_i \le n,\quad 1 \le a_i \le 100. $