고양이 냄비 개조 계획 (가칭)

당신은 집에서 많은 고양이를 기르고 있습니다. 매일 하는 일은 고양이가 토기 냄비 안에 들어가 낮잠 자는 모습을 촬영하는 것입니다(일명 고양이 냄비). 여러 마리의 고양이가 냄비 안에서 함께 몸을 말고 자는 모습은 정말 사랑스럽습니다.

각 고양이에는 무게 $m_i$와 Cute $c_i$가 정해져 있습니다. Cute는 고양이 한 마리만 봤을 때의 사랑스러움, 앳됨, 유연함, 부드러움, 풋풋함 등을 종합적으로 평가한 값이며, 클수록 그 고양이가 매력적입니다.

고양이 냄비에는 UnCute라는 값도 정해져 있습니다. 냄비 전체의 불균형을 나타내는 값으로, Cute와 반대로 작을수록 좋은 고양이 냄비입니다. 냄비의 UnCute는 안에 있는 고양이 Cute의 최댓값 $C_{\max}$와 최솟값 $C_{\min}$을 사용해 $C_{\max} - C_{\min}$으로 나타냅니다. 즉, 안에 있는 고양이들의 Cute가 모두 비슷한 냄비가 좋은 냄비입니다.

고양이 냄비를 들고 다닐 때를 생각하면, 냄비의 무게(안에 있는 고양이 무게의 합)는 한계값 $W$ 이하여야 합니다. 이 조건을 만족하도록 냄비에 넣을 고양이를 골라 냄비의 UnCute를 최대한 작게 만들고 싶은데, 얼마나 작게 만들 수 있을까요?

이 문제를 풀고 만족하던 것은 옛날 일입니다. 얼마 전 창고를 정리하다가 낡은 토기 냄비를 발견했습니다. 이제 집에 토기 냄비가 두 개입니다. 바로 듀얼 고양이 냄비의 시대입니다. 평범한 고양이 냄비는 이미 낡았습니다.

듀얼 고양이 냄비에서 토기 냄비 $A$에는 수컷 고양이만, 다른 토기 냄비 $B$에는 암컷 고양이만 들어갑니다. 듀얼 고양이 냄비의 UnCute는 Cute의 불균형뿐 아니라 두 냄비 무게의 불균형도 고려해야 합니다. 무거운 쪽 냄비의 무게를 $M_{\max}$, 가벼운 쪽 냄비의 무게를 $M_{\min}$이라 하면(두 냄비 무게가 같으면 $M_{\max} = M_{\min}$), 듀얼 고양이 냄비의 UnCute는

$\max\{M_{\max} - M_{\min}, C_{\max} - C_{\min}\}$

입니다. 여기서 $C_{\max}$와 $C_{\min}$은 냄비 $A$ 또는 냄비 $B$ 안에 있는 고양이들의 Cute 최댓값과 최솟값입니다.

고양이 냄비를 들고 다니므로 $M_{\max}$는 한계값 $W$ 이하여야 합니다. 이 조건을 만족하도록 듀얼 고양이 냄비에 들어갈 고양이를 골라 UnCute를 최대한 작게 만들고 싶은데, 얼마나 작게 만들 수 있을까요?

첫 줄에는 정수 $N_A$($1 \le N_A \le 500$), $N_B$($1 \le N_B \le 500$), $W$($1 \le W \le 10{,}000$)가 공백으로 구분되어 주어집니다. $N_A$는 수컷 고양이의 총 마리 수, $N_B$는 암컷 고양이의 총 마리 수, $W$는 고양이 냄비의 무게 한계값입니다.

이어지는 $N_A$개의 줄에는 정수 $m_{A,i}$($1 \le m_{A,i} \le 10{,}000$)와 $c_{A,i}$($1 \le c_{A,i} \le 10^9$)가 공백으로 구분되어 주어집니다. $i$번째 수컷 고양이의 무게는 $m_{A,i}$, Cute는 $c_{A,i}$입니다.

이어지는 $N_B$개의 줄에는 정수 $m_{B,i}$($1 \le m_{B,i} \le 10{,}000$)와 $c_{B,i}$($1 \le c_{B,i} \le 10^9$)가 공백으로 구분되어 주어집니다. $i$번째 암컷 고양이의 무게는 $m_{B,i}$, Cute는 $c_{B,i}$입니다.

수컷 고양이와 암컷 고양이 각각에 무게가 $W$ 이하인 고양이가 1마리 이상 있다고 가정해도 됩니다.

NA NB W
mA,1 cA,1
...
mA,NA cA,NA
mB,1 cB,1
...
mB,NB cB,NB

$M_{\max}$가 $W$를 넘지 않는다는 조건에서 듀얼 고양이 냄비의 UnCute 최솟값을 출력하세요. 단, 두 고양이 냄비에 모두 고양이가 1마리 이상 들어 있어야 합니다.