题目描述

小爱在野外游玩时，手机没电了，幸好，他带了一些充电宝。

已知市面上一共有 $n$ 种型号的充电宝，其中型号为 $i$ 的充电宝中每 $1\%$ 的电量可以使小爱的手机继续使用 $x_i$ 秒。

小爱有 $m$ 个充电宝，其中第 $i$ 个充电宝的型号为 $t_i$ ，剩余电量为 $a_i\%$ 。他按给定顺序使用充电宝，当一个充电宝的电量耗尽时，会选择换一个充电宝接着使用。（假设充电宝在不使用的时候不会有电量损耗）。

请你帮小爱计算出他的手机还能继续使用多长时间。

输入格式

第一行两个用空格隔开的正整数 $n,m$ 。

第二行 $n$ 个用空格隔开的正整数，其中第 $i$ 个表示 $x_i$ 。

接下来 $m$ 行，每行两个用空格隔开的正整数，其中第 $i$ 行按顺序表示 $t_i,a_i$ 。

输出格式

输出共一行，一个整数，表示小爱的手机还能继续使用的时间。

样例

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

50000

解释#1

第 1 个充电宝能使用 10000 秒 第 2 个充电宝能够使手机继续使用 30000 秒 第 3 个充电宝能够使手机继续使用 4000 秒 第 4 个充电宝能够使手机继续使用 6000 秒 所以用上所有的充电宝能够使手机继续使用 50000 秒。

数据范围

$n≤500,m≤10^4,1≤x_i≤600,1≤t_i≤n,1≤a_i≤10^5$。