Nutritious Diet

Problem Description

Mr. L is carrying out his weight-gain plan.

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

Mr. L's research shows that a truly nutritious diet forbids eating more than a certain number of servings of a given food type at once. For example, in one meal, meat should not exceed $1$ serving, fish should not exceed $1$ serving, eggs should not exceed $1$ serving, and vegetables should not exceed $2$ servings.

Mr. L wants to eat as much fat as possible under a nutritious diet, but of course his appetite is also limited.

Input Format

The first line contains three positive integers $n, m, k$: Mr. L can eat at most $m$ servings per meal, there are $n$ kinds of food to choose from, and these $n$ foods are divided into $k$ categories.

The second line contains $k$ positive integers not exceeding $10$: the maximum number of servings allowed for categories $1$ to $k$.

The following $n$ lines each contain two positive integers: the fat index $a_i$ and the category $b_i$ of that food.

Output Format

One number: the maximum total fat index Mr. L can eat.

Sample Input

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

Sample Output

60

Constraints

For $100\%$ of the data: $1\le n\le 200$, $1\le m\le 100$, $1\le k\le 100$, $1\le a_i\le 100$, $1\le b_i\le k$.