zjy 的套圈计划 1568

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：10 AC：8 Score：100

Description

众所周知 zjy 很喜欢吃羊腿

今天老板又出了一个新活动：套羊腿

这个游戏是这么玩的，有一些大小不一，价格也不同的羊腿，老板会给 zjy 一些圈圈，如果 zjy 能用圈圈套中某只羊腿，那这只羊腿就归他了

现在 zjy 为了这个游戏，专门苦练了好多天，已经能够做到无限精准，指哪打哪了！但是圈圈的大小必须要严格大于羊腿的大小，才能套中

现在 zjy 知道自己手里的圈圈大小分别为多少，也知道每只羊腿的大小以及价格

现在 zjy 想知道，他能套到总价最高的羊腿价值和是多少？

当然，如果 zjy 套走了某只羊腿，家大业大的老板会立刻在同一个位置补上一只相同大小并且相同价格的羊腿

Input

第一行两个整数 $N$，$M$ 代表圈圈的个数和羊腿的个数。

第二行 $N$ 个整数代表圈圈的大小 $r_c$。

接下来 $M$ 行每行两个整数 $r_b$，$v$ 代表这只羊腿的大小 $r$ 和价格 $v$。

对于 $30\%$ 的数据：$N = 1$ , $M = 1$ , $1 \le r_c , r_b , v \le 100$ 。

对于 $60\%$ 的数据：$1 \le N \times M \le 1000000$, $1 \le r_c , r_b , v \le 100$ , 保证所有的价值 $v$ 都相等。

对于 $100\%$ 的数据：$1 \le N \times M \le 1000000$, $1 \le r_c , r_b , v \le 100$。

Output

输出一个整数，代表徐老师能获得的最大价值。

Samples

input:

2 2 2 3 1 2 2 3

output: