Ненад је отпутовао у Париз и жели да купи поклоне својим родитељима. Пошто путује нискотарифном авио-компанијом, ограничена је маса коју може да понесе у свом ранцу. Оцу ће купити поклон у једној, а мајци у другој продавници. Напиши програм који на основу познатих маса и цена поклона у обе продавнице помаже Ненаду да родитељима купи што вредније поклоне (гледајући њихову укупну цену).

Улаз

Са стандардног улаза се уносе подаци у производима у две продавнице. За сваку продавницу се уноси број производа \(n\) \((1 \leq n \leq 10^5)\), и затим у наредних \(n\) линија по два цела броја, сваки између \(1\) и \(10^9\), који представљају масу и затим цену производа. Након тога се уноси и укупна маса поклона коју је могуће понети у ранцу (цео број између 1 и \(2\cdot 10^9\)).

Излаз

На стандардни излаз исписати највећи могући збир цена првог и другог поклона које је могуће понети у ранцу.

Пример

Улаз

3
2 4
3 6
4 5
3
2 3
3 2
4 5
6

Излаз

9

Овај задатак има и другачија решења у делу збирке који следи.