题目描述

求 01 背包前 $K$ 优解的价值和。

DD 和好朋友们要去爬山啦！

他们一共有 $K$ 个人，每个人都会背一个包。这些包的容量是相同的，都是 $V$。可以装进背包里的一共有 $N$ 种物品，每种物品都有给定的体积和价值。

在 DD 看来，合理的背包安排方案是这样的：每个人背包里装的物品的总体积恰等于包的容量。每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。

任意两个人，他们包里的物品清单不能完全相同。在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？

输入格式

第一行三个数 $K,V,N$。

接下来 $N$ 行每行两个数，表示体积和价值。

输出格式

共一行，一个整数，表示前 $K$ 优解的价值和。

输入输出样例

2 10 5
3 12
7 20
2 4
5 6
1 1

57

说明/提示

对于 $100\%$ 的数据，$K\le 50$，$V\le 5000$，$N\le 200$。

GESPOJ 可见测试数据

以下数据是本题实际评测数据的一部分。

1 1 1
1 33439

33439

13 595 17
467 99711
595 92599
595 89858
595 4140
595 45868
252 64472
595 52240
128 31863
595 78493
595 1024
595 89767
595 8717
595 21817
595 31941
595 568
9 3425
595 11972

660010