射箭游戏

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Alice正在玩一个射箭游戏。

现在Alice有 N 枝不同的箭,每只箭有它的攻击力。

有 M 个怪物,每个怪物有它的生命值,击杀怪物后会掉落金币。

每只箭最多使用一次,每个怪物最多被攻击一次。

且为了“简单”起见,怪物掉落金币数等于其生命值

问Alice最多可以获得多少金币。

Input

输入数据共三行。

第一行有两个正整数N和M,分别表示箭的数量和怪物的数量。(1 <= N <= 1000000, 1 <= M <= 1000000)

第二行有N个正整数,第 i 个数表示第 i 枝箭的攻击力 。(1 <= 攻击力 <= 1000000000)

第三行有M个正整数,第 i 个数表示第 i 个怪物的生命值和掉落金币数 。 (1 <= 生命值 <= 1000000000)

友情提示:答案会超出int范围,请使用长整形 long long(%lld) 进行计算。

Output

输出一个整数,表示Alice最多可以获得多少金币。

Sample Input

5 5
1 4 5 7 9
2 10 8 6 4

Sample Output

20

Hint

Source

lxw