Problem Description

You are to create a course by selecting dishes from $ N $ types of main dishes and $ M $ types of side dishes. You can only choose one type of main dish, but you can choose any number of side dishes. It is also acceptable not to choose any side dishes. For both main dishes and side dishes, only one of each type can be included in the course.

• The $ i $th main dish has a price of $ A_i $ and a customer rating of $ B_i $.
• The $ i $th side dish has a price of $ C_i $ and a customer rating of $ D_i $.

The total price and rating of the course are determined by the sum of the main dish and side dishes. When the total price of the course must be $ L $ or less, find the maximum possible rating of the course.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ L $ $ A_1 $ $ B_1 $ : $ A_N $ $ B_N $ $ C_1 $ $ D_1 $ : $ C_M $ $ D_M $

• The first line contains three integers $N\ (1\ ≦\ N\ ≦\ 10,000)$, $M\ (1\ ≦\ M\ ≦\ 1,000)$, $L\ (1\ ≦\ L\ ≦\ 10,000)$ separated by spaces.
• The next $ N $ lines contain information about the main dishes. The $i\ (1\ ≦\ i\ ≦\ N)$th line contains two integers representing the price and rating of the $ i $th main dish, $A_i\ (1\ ≦\ A_i\ ≦\ 10,000)$, $B_i\ (1\ ≦\ B_i\ ≦\ 10,000)$.
• The next $ M $ lines contain information about the side dishes. The $i\ (1\ ≦\ i\ ≦\ M)$th line contains two integers representing the price and rating of the $ i $th side dish, $C_i\ (1\ ≦\ C_i\ ≦\ 10,000)$, $D_i\ (1\ ≦\ D_i\ ≦\ 10,000)$.
• It is guaranteed that a course can always be created.

Output Format

Output the maximum rating of the course in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

2 2 10
2 3
3 6
3 5
5 5

Sample Output #1

13

Sample Input #2

3 3 10
1 1
2 3
3 5
4 8
5 10
6 12

Sample Output #2

19

Sample Input #3

3 3 10
1 1
11 11
11 11
11 11
11 11
11 11

Sample Output #3

1

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分