Description

Compute the sum of values of the top $K$ solutions to the 0/1 knapsack.

DD and their friends are going hiking!

There are $K$ people in total, and each person will carry one backpack. All backpacks have the same capacity $V$. There are $N$ types of items that can be put into a backpack, and each type has a given volume and value.

According to DD, a reasonable packing plan is as follows: the total volume of items in each person’s backpack is exactly equal to the backpack’s capacity. In each backpack, there is at most one copy of each item type, but the same item type may appear in different backpacks.

For any two people, their item lists must not be exactly the same. Under these requirements, what is the maximum possible total value of all items across all $K$ backpacks?

Input Format

The first line contains three integers $K$, $V$, $N$.

The next $N$ lines each contain two integers, the volume and the value of an item type.

Output Format

Output a single integer on one line: the sum of values of the top $K$ solutions.

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

57

Hint

For $100\%$ of the testdata, $K \le 50$, $V \le 5000$, $N \le 200$.

Translated by ChatGPT 5