B. Значимые кубки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Степан — опытный участник олимпиад. У него есть n кубков за олимпиады по физике и m — по информатике. Каждый кубок характеризуется двумя параметрами — своей значимостью ci и шириной wi.

Степан решил выставить часть своих кубков на полке общей ширины d так, чтобы:

  • на полке был хотя бы один кубок по физике и хотя бы один кубок по информатике,
  • суммарная ширина выставленных кубков не превышала d,
  • от каждого предмета были выставлены несколько самых значимых кубков (то есть, если по какому-то предмету выставлен кубок с значимостью x, то должны быть выставлены все кубки по этому предмету, чья значимость превышает x).

Перед вами стоит задача определить максимально возможную суммарную значимость кубков, которые Степан может выставить на полку ширины d, учитывая все описанные выше условия.

Входные данные

В первой строке следует три целых числа 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-го кубка по информатике.

Выходные данные

Выведите максимально возможную суммарную значимость кубков, которые Степан может выставить на полку ширины d, учитывая все необходимые требования.

Если не существует ни одного способа выставить кубки, выведите 0.

Примеры
Входные данные
3 1 8
4 2
5 5
4 2
3 2
Выходные данные
8
Входные данные
4 3 12
3 4
2 4
3 5
3 4
3 5
5 2
3 4
Выходные данные
11
Входные данные
2 2 2
5 3
6 3
4 2
8 1
Выходные данные
0
Примечание

В первом примере у Степана есть всего один кубок по информатике, который обязательно нужно выставить. Его значимость равна 3, а ширина 2, поэтому после его выставления ширина оставшегося места на полке равна 6. Также Степан должен выставить второй кубок с шириной 5 по физике, так как он самый значимый (его значимость равна 5). После этого на полку больше нельзя поставить ни одного кубка. Поэтому максимальная суммарная значимость выставленных кубков равна 8.