Description

大袜子之神得知小美剪了袜子，非常生气，一怒之下，怒了一下，然后叫来了一群大袜子之神，这群大袜子之神总共有n种,每种大袜子神都有无数个，每种大袜子神都有自己的攻击力和防御力。大袜子神王觉得如果全部大袜子神全部出动的话，太欺负小美了，所以决定派出m个大袜子神，指派规则如下：大袜子神王说出一个数字a，然后可以派出一个攻击力为a或者防御力为a的大袜子神，这个操作会执行m次，然后总共派出m个大袜子神。

请你帮大袜子神王计算一下，最后派出的m个大袜子神的攻击力和防御力总和最高为多少。

输入样例1

3 2

1 2

1 3

3 2

1 3

输出样例1

9

样例解释1

可以派出第二个和第三个大袜子神，这样全部大袜子神的攻击力和防御总和最高为9。

输入样例2

5 3

1 3

3 4

2 5

2 9

1 10

1 5 2

输出样例2

29

Input Format

第一行输入两个数字，分别是n和m，代表大袜子神的种类，和一共派出m个大袜子神

第二行到第n+1行，每行两个数字，分别代表每种大袜子神的攻击力和防御力。

最后再输入一行，包含m个正整数，代表大袜子神王每次说出的数字。

数据范围

对于  60%的数据保证：

n<=10000,m<=1000

每种大袜子神的攻击力在1到100范围内。

每种大袜子神的防御力在1到100范围内。

对于  100%的数据保证：

n<=100000,m<=10000

每种大袜子神的攻击力在1到10000范围内。

每种大袜子神的防御力在1到10000范围内。

对于所有数据保证：

大袜子神王说出的数字都是合法的，即肯定存在一种大袜子神，他的攻击力或者防御力是大袜子神王喊出的数字。

Output Format

输出一个整数，表示派出的m个大袜子神的攻击力和防御力总和最高为多少

3 2
1 2
1 3
3 2
1 3

9

Source

佛山市青少年科技素养创意挑战赛 五年级模拟题