#P2095. 营养膳食

营养膳食

题目描述

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

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

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

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

输入格式

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

第二行包含 kk 个不超过 1010 的正整数,表示可以吃 11kk 类食品的最大份数。

接下来 nn 行每行包括 22 个正整数,分别表示该食品的脂肪指数 aia_i 和所属的类别 bib_i

输出格式

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

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

提示

对于 100%100\% 的数据,1n2001\leq n\leq 2001m1001\leq m\leq 1001k1001\leq k\leq 1001ai1001\leq a_i\leq 1001bik1\leq b_i\leq k