Significant Cups

Description:

Input:

The first line contains three integers n, m and d (1 ≤ n, m ≤ 100 000, 1 ≤ d ≤ 10⁹) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf.

Each of the following n lines contains two integers c_i and w_i (1 ≤ c_i, w_i ≤ 10⁹) — significance and width of the i-th cup for Physics olympiads.

Each of the following m lines contains two integers c_j and w_j (1 ≤ c_j, w_j ≤ 10⁹) — significance and width of the j-th cup for Informatics olympiads.

Output:

Print the maximum possible total significance, which Stepan can get exposing cups on the shelf with width d, considering all the rules described in the statement.

If there is no way to expose cups on the shelf, then print 0.

Sample Input:

3 1 8
4 2
5 5
4 2
3 2

Sample Output:

8

Sample Input:

4 3 12
3 4
2 4
3 5
3 4
3 5
5 2
3 4

Sample Output:

11

Sample Input:

2 2 2
5 3
6 3
4 2
8 1

Sample Output:

0

Note:

In the first example Stepan has only one Informatics cup which must be exposed on the shelf. Its significance equals 3 and width equals 2, so after Stepan exposes it, the width of free space on the shelf becomes equal to 6. Also, Stepan must expose the second Physics cup (which has width 5), because it is the most significant cup for Physics (its significance equals 5). After that Stepan can not expose more cups on the shelf, because there is no enough free space. Thus, the maximum total significance of exposed cups equals to 8.