疯狂的小金

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

自从听说小白和小黑的友谊的小船翻了以后,小金很是开心,就和小白建立了小船,但是现在小金看到天上的n只小鸟,就萌生了一个疯狂的想法,他决定带着小白去打鸟,所以小金去商店买装备--->箭,现在他知道每只鸟的防御力,和每一只箭的攻击力和价值。如果箭的攻击力小于鸟的防御了,小鸟是不会被打下来的。最为奇葩的是每种箭只有一只,小金想将小鸟都打下来,如果不能那么小金和小白的小船又要翻啦。当然小金的资金最近比较的紧张,所以他想花费最小的钱。

Input

多组输入,每组第一行输入两个数n,m(1<=n,m<=50000),表示小鸟的数量和箭的数量。接下来的一行的n个数表示每一个小鸟的防御力,接下来的m行,每行两个数,表示箭的攻击力v价值w,(1<=v,w<=100000).

Output

如果小金不能将所有的小鸟射下来,输出"No Solution"。否则输出最小的花费。

Sample Input

3 3
1 2 3
2 1
3 2
4 3

Sample Output

6

Hint

Source

“师创杯”山东理工大学第八届ACM程序设计竞赛