4339: Significant Cups重要奖杯

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:4 通过:4

题目描述

B. Significant Cups
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
斯特潘是一位经验丰富的奥运选手。他有n杯物理奥林匹克和m杯信息学奥林匹克。每个杯子都有两个参数——其重要性ci和宽度wi。


Stepan决定将他的一些杯子放在宽度为d的架子上,这样:
·货架上有至少一个物理学杯和至少一个信息学杯,
·暴露的杯的总宽度不超过d,
·从每个科目(物理和信息学)中,一些最重要的杯子被暴露出来(即,如果某个科目的杯子具有显著性x,那么该科目的所有杯子都必须具有显著性大于x)。

考虑到上述所有规则,你的任务是确定最大可能的总体意义,当Stepan将杯子放在宽度为d的架子上时,他可以得到最大可能的总意义。总意义是所有暴露杯子的意义之和。
Stepan is a very experienced olympiad participant. He has n cups for Physics olympiads and m cups for Informatics olympiads. Each cup is characterized by two parameters − its significance ci and width wi.
Stepan decided to expose some of his cups on a shelf with width d in such a way, that:
  • there is at least one Physics cup and at least one Informatics cup on the shelf,
  • the total width of the exposed cups does not exceed d,
  • from each subjects (Physics and Informatics) some of the most significant cups are exposed (i. e. if a cup for some subject with significance x is exposed, then all the cups for this subject with significance greater than x must be exposed too).
Your task is to determine the maximum possible total significance, which Stepan can get when he exposes cups on the shelf with width d, considering all the rules described above. The total significance is the sum of significances of all the exposed cups.
Input
The first line contains three integers n, m and d (1≤n,m≤100000, 1≤d≤109) − 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 ci and wi (1≤ci,wi≤109) − significance and width of the i-th cup for Physics olympiads.
Each of the following m lines contains two integers cj and wj (1≤cj,wj≤109) − 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.
Examples
Input
3 1 8
4 2
5 5
4 2
3 2
Output
8
Input
4 3 12
3 4
2 4
3 5
3 4
3 5
5 2
3 4
Output
11
Input
2 2 2
5 3
6 3
4 2
8 1
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.


输入格式

第一行包含三个整数n、m和d(1 ≤ n, m ≤ 100 000, 1 ≤ d ≤ 109)-物理奥林匹克竞赛的杯数、信息学奥林匹克竞赛的杯子数和货架宽度。
以下n行中的每一行包含两个整数ci和wi(1 ≤ ci, wi ≤ 109)-第i届物理奥林匹克杯的意义和宽度。
以下m行中的每一行包含两个整数cj和wj(1 ≤ cj, wj ≤ 109)-第j届信息学奥林匹克杯的意义和宽度。

输出格式

考虑到声明中描述的所有规则,打印出Stepan可以将杯子放在宽度为d的架子上的最大可能总重要性。
如果无法将杯子暴露在架子上,请打印0。

输入样例 复制

3 1 8
4 2
5 5
4 2
3 2

输出样例 复制

8