あなたは、自宅にたくさんのねこを飼っている。そんなあなたの日課は、飼っているねこが土鍋の中 に入って昼寝している様子（通称：ねこ鍋）を撮影することだ。何匹かのねこが、鍋の中でいっしょ に丸くなって眠る姿は、実に愛くるしい。
それぞれのねこには、「重さ」mi と「Cute」ci が定義されている。Cute とは、そのねこ1 匹だけを見たときの、愛らしさ・あどけなさ・しなやかさ・やわらかさ・ういういしさ、などを総合的に評価した数値であり、大きければ大きいほどそのねこは魅力的である。
また、ねこ鍋に対しては「UnCute」という数値が定義される。これは、ねこ鍋全体としてのアンバラ ンスさをあらわす値であり、Cute とは逆に、小さければ小さいほど、そのねこ鍋はよいねこ鍋であ る。ねこ鍋のUnCute は、中にいるねこのCute の最大値Cmax と最小値Cmin を用いて、Cmax - Cminとあらわされる。つまり、中にいるねこがみな同じくらいのCute を持っているねこ鍋が、よいねこ鍋である。
ねこ鍋を持ち運ぶときのことを考えると、ねこ鍋の重さ（＝中にいるねこの重さの総和）は、限界値 W 以下でなければならない。この条件をみたすようにねこ鍋に入ってもらうねこを選んで、ねこ鍋のUnCute を小さくしたいのだが、いったいどこまで小さくできるのだろうか。
……という問題を解いてすっかり満足した気になっていたのは、過去の話だ。
この前、あなたが家の倉庫を整理していたら、倉庫の中から古ぼけた土鍋が見つかった。これであな たの家にある土鍋は２つ。そう、これからは、デュアルねこ鍋の時代なのだ！ ただのねこ鍋なども う古い！
デュアルねこ鍋では、土鍋A はオスのねこ専用、もう片方の土鍋B はメスのねこ専用である。また、 デュアルねこ鍋のUnCute を定義するにあたっては、Cute のアンバランスさだけではなく、２つの ねこ鍋の重さのアンバランスさも考慮に入れる必要がある。具体的には、重いほうのねこ鍋の重さを Mmax、軽いほうのねこ鍋の重さをMmin とおくと（２つのねこ鍋の重さが同じときはMmax = Mmin）、デュアルねこ鍋のUnCute は、
max{Mmax - Mmin, Cmax - Cmin}
とあらわされる。なお、ここでのCmax とCmin は、ねこ鍋A の中またはねこ鍋B の中にいるねこのCute の最大値,最小値である。
ねこ鍋を持ち運ぶときのことを考えると、Mmaxは、限界値W 以下でなければならない。この条件をみたすようにデュアルねこ鍋に入ってもらうねこを選んで、デュアルねこ鍋のUnCute を小さくしたいのだが、いったいどこまで小さくできるのだろうか。
NA NB W
mA,1 cA,1
mA,2 cA,2
.
.
.
mA,NA cA,NA
mB,1 cB,1
mB,2 cB,2
.
.
.
mB,NB cB,NB
入力の１行目には、整数NA（1 ≤ NA ≤ 500）と整数NB（1 ≤ NB ≤ 500）と整数W（1 ≤ W ≤ 10,000）が、空白区切りで書かれている。これは、あなたが飼っているオスのねこが全部でNA 匹、メスのねこが全部でNB 匹いることをあらわす。W はねこ鍋の重さの限界値である。
続くNA 行には、整数mA,i（1 ≤ mA,i ≤ 10,000）と整数cA,i（1 ≤ cA,i ≤ 1,000,000,000）が、空白区切りで書かれている。１＋ i 行目に書かれた整数mA,i とcA,i は、i 番目のオスのねこの重さがmA,i、Cute がcA,i であることをあらわす。
続くNB 行には、整数mB,i（1 ≤ mB,i ≤ 10,000）と整数cB,i（1 ≤ cB,i ≤ 1,000,000,000）が、空白区切りで書かれている。１＋ NA ＋ i 行目に書かれた整数mB,i とcB,i は、i 番目のメスのねこの重さがmB,i、Cute がcB,i であることをあらわす。
オスのねこにもメスのねこにも、重さがW 以下であるようなねこが、それぞれ１匹以上は存在すると仮定してよい。
Mmax がW を超えないという条件のもとで、デュアルねこ鍋のUnCute の最小値を出力せよ。ただし、どちらのねこ鍋にも１匹以上のねこが入っていなければならない。
4 3 12 3 6 2 4 7 9 10 1 6 5 8 4 15 19
2
1 3 10 1 15 6 8 5 9 8 7
6
8 6 65 30 98 27 51 4 74 65 87 49 19 27 48 43 7 35 28 43 69 8 47 64 75 18 23 54 29 40 43
8