题目描述

曲老师发现自己的体重已经低于200斤了，为了避免减肥导致的松弛，曲老师觉得还是需要增肌。

为了增肌，需要吃到更多的蛋白质，但是也不能只吃蛋白质，那样就会缺少其他的物质。

经过研究发现：对于某类的食物，不能一次性吃太多，例如一顿饭不能吃超过1份肉，不能超过吃一份奶，不能吃超过一份蛋类。

曲老师想要在他胃口能吃下的情况下，比较健康的吃到更多的蛋白质

输入格式

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

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

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

输出格式

包括一个数字即曲老师可以吃到的最大蛋白质指数和。

样例 #1

样例输入 #1

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

样例输出 #1

60

提示

对于 $20\%$ 的数据，$m = n = k$，且吃每种种类的食品最大份数均大于等于1;

对于 $40\%$ 的数据，吃 $1$ 到 $k$ 类食品的最大份数均为10，且$m\leq 10$;

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