Description

Mr. L is working on his weight gain plan.

To gain weight, Mr. L wants to eat more fat. However, he cannot eat only high-fat foods, otherwise he would lack other nutrients.

Through research, Mr. L found that a truly balanced diet sets an upper limit on the number of servings of each category in a single meal. For example, for one meal: at most $1$ serving of meat, at most $1$ serving of fish, at most $1$ serving of eggs, and at most $2$ servings of vegetables.

Mr. L wants to maximize fat intake while following a nutritional diet, and of course his capacity is limited.

Input Format

The first line contains three positive integers $n$, $m$ and $k$. Here, $m$ is the maximum number of servings Mr. L can eat in one meal; there are $n$ foods to choose from, and these $n$ foods fall into $k$ categories.

The second line contains $k$ positive integers, each not exceeding $10$, where the $i$-th number gives the maximum number of servings allowed for category $i$ in a single meal, for categories $1$ through $k$.

Each of the next $n$ lines contains $2$ positive integers: the fat index $a_i$ of that food and its category $b_i$.

Output Format

Output a single integer: the maximum possible total fat index that Mr. L can eat.

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

60

Hint

For $100\%$ of the testdata, $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$.

Translated by ChatGPT 5