Significant Cups
Contest: VK Cup 2017 - Wild Card Round 1
Difficulty rating: 2100
Tags: *special, binary search, data structures, two pointers

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 format:
The first line contains three integers n, m and d (1 ≤ n, m ≤ 100 000, 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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
3 1 8
4 2
5 5
4 2
3 2

Example output:
8

Example input:
4 3 12
3 4
2 4
3 5
3 4
3 5
5 2
3 4

Example output:
11

Editorial:
Изначально отсортируем информацию о кубках как пары (для каждого предмета отдельно) — сначала по невозрастанию значимостей, а при их равенстве по неубыванию их ширины.
Затем линейно предпосчитаем массивы ca, wa, cb и wb, где cai равно суммарной значимости первых i отсортированных кубков по физике, а wai — их суммарная ширина. Массивы cb и wb — аналогичны, но они хранят информацию о кубках по информатике.
Переберем cnt — сколько самых значимых кубков мы возьмем по физике (они отсортированны именно в этом порядке). Тогда, если мы их ставим, можно легко получить их суммарную значимость (это cacnt) и ширину (это wacnt). Тогда на полке останется d - wacnt свободного места. С помощью бинарного поиска определим, сколько самых значимых кубков по информатике поместится на полке. Пусть это количество равно p. Тогда, если p больше единицы (ведь мы обязательно должны взять по одному кубку от каждого предмета), обновим ответ величиной cacnt + cbp.