3715 - 消灭兔子
Description

有 N 只兔子,每只有一个血量 B[i],需要用箭杀死。有 M 种不同类型的箭,每种箭有伤害 D[i] 和价格 P[i]。每种箭只能用一次,每只兔子也只能被射一次,计算消灭所有兔子最少需要多少 Q 币。如不能杀死所有兔子输出 No Solution。(箭伤害 >= 兔子血量即可杀死;B[i], D[i], P[i] 均 <= 100000)

Input

第 1 行两个整数 N, M (1 <= N, M <= 50000)。
第 2-N+1 行每行 1 个正整数表示兔子血量 B[i]。
第 N+2-N+M+1 行每行 2 个正整数 D[i] P[i]。

Output

输出最少 Q 币数;不能杀死所有兔子则输出 No Solution。

Examples

Input

3 3
1
2
3
2 1
3 2
4 3

Output

6
Hint

箭按伤害降序、兔子按血量降序,逐个兔子把伤害 >= 血量的箭价格入小顶堆取最便宜;堆空则无解。

Source
51nod 1191
Tags
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1