题目描述

Mr.L正在完成自己的增肥计划。

为了增肥，Mr.L希望吃到更多的脂肪。然而也不能只吃高脂肪食品，那样的话就会导致缺少其他营养。

Mr.L通过研究发现：真正的营养膳食规定某类食品不宜一次性吃超过若干份。比如就一顿饭来说，肉类不宜吃超过1份，鱼类不宜吃超过1份，蛋类不宜吃超过1份，蔬菜类不宜吃超过2份。

Mr.L想要在营养膳食的情况下吃到更多的脂肪，当然Mr.L的食量也是有限的。

输入格式

第一行包含三个正整数n,m和k。表示Mr.L每顿饭最多可以吃m份食品，同时有n种食品供Mr.L选择，而这n种食品分为k类。

第二行包含k个不超过10的正整数，表示可以吃1到k类食品的最大份数。

接下来n行每行包括2个正整数，分别表示该食品的脂肪指数a_i和所属的类别b_i。

输出格式

包括一个数字即Mr.L可以吃到的最大脂肪指数和。

输入样例 #1

6 6 3
3 3 2
15 1
15 2
10 2
15 2
10 2
5 3

输出样例 #1

60

输入样例 #2

3 3 3
1 1 1
5 1
6 2
7 3

输出样例 #2

18

输入样例 #3

4 2 2
1 2
100 1
90 1
80 2
70 2

输出样例 #3

180

提示

说明/提示

对于100%的数据，1≤n≤200，1≤m≤100，1≤k≤100，1≤a_i≤100，1≤b_i≤k。

数据范围

第二行包含k个不超过10的正整数，表示可以吃1到k类食品的最大份数。

对于100%的数据，1≤n≤200，1≤m≤100，1≤k≤100，1≤a_i≤100，1≤b_i≤k。