Description

有n只怪兽，每个怪兽有一个HP[i].
商店有m个不同的水果，用来砸怪兽。
水果有一个杀伤力val和一个价格pri，当某一个水果的杀伤力大于或者等于怪兽的HP的时候该怪兽会被消灭。
一个水果只能用来砸一只怪兽，一个怪兽也只能被一个水果砸。
求使得所有怪兽被消灭的最小花费。

Format

Input

第一行两个正整数n，m（1<=n,m<=50005）
接下来一行n个正整数，表示n个怪兽们的HP(1<=HP<=100000)
接下来m行每行两个正整数val，pri，表示第i种水果的杀伤力和价格。(1<=val,pri<=100000)

Output

若存在答案则输出一个正整数ans即最小花费，否则输出“No Solution”（不含引号）。

Sample 1

Input

3 3
1
2
3
2 1
3 2
4 3

Output

6

Limitation

1s, 64Mb for each test case.

Source

Vijos Original