Cat Pot Remodeling Plan (Tentative)

You keep many cats at home. Your daily routine is to photograph your cats napping curled up inside a clay pot, which you call a cat pot. When several cats sleep together in the pot, it is very lovely.

Each cat has a weight $m_i$ and a Cute value $c_i$. Cute is an overall rating of how lovable, innocent, graceful, soft, and fresh a single cat looks on its own. The larger the Cute, the more attractive the cat.

A cat pot also has a value called UnCute, which measures how unbalanced the pot is. Unlike Cute, a smaller UnCute means a better cat pot. The UnCute of a pot is $C_{\max} - C_{\min}$, where $C_{\max}$ and $C_{\min}$ are the largest and smallest Cute among the cats inside. In other words, a good pot holds cats with similar Cute values.

When carrying a cat pot, the total weight of the cats inside, which is the pot weight, must not exceed the limit $W$. You want to choose the cats for the pot so that its UnCute is as small as possible. How small can it get?

You once thought solving this problem was enough. Then you found an old clay pot while cleaning the storehouse. Now you have two clay pots at home, so the era of the dual cat pot has begun. The ordinary cat pot is already outdated.

In a dual cat pot, pot $A$ is for male cats only, and pot $B$ is for female cats only. The UnCute of a dual cat pot must account for the imbalance in weight between the two pots, not only the imbalance in Cute. Let $M_{\max}$ be the weight of the heavier pot and $M_{\min}$ the weight of the lighter pot (if both pots weigh the same, $M_{\max} = M_{\min}$). The UnCute of a dual cat pot is

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

Here $C_{\max}$ and $C_{\min}$ are the largest and smallest Cute values among the cats in pot $A$ or pot $B$.

Since the pots are carried around, $M_{\max}$ must not exceed the limit $W$. Choose the cats for the dual cat pot so that its UnCute is as small as possible. How small can it get?

The first line contains three integers $N_A$ ($1 \le N_A \le 500$), $N_B$ ($1 \le N_B \le 500$), and $W$ ($1 \le W \le 10{,}000$), separated by spaces. $N_A$ is the number of male cats, $N_B$ is the number of female cats, and $W$ is the weight limit of a pot.

The next $N_A$ lines each contain $m_{A,i}$ ($1 \le m_{A,i} \le 10{,}000$) and $c_{A,i}$ ($1 \le c_{A,i} \le 10^9$), the weight and Cute of the $i$-th male cat.

The next $N_B$ lines each contain $m_{B,i}$ ($1 \le m_{B,i} \le 10{,}000$) and $c_{B,i}$ ($1 \le c_{B,i} \le 10^9$), the weight and Cute of the $i$-th female cat.

At least one male cat and at least one female cat have weight at most $W$.

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

Print the minimum possible UnCute of the dual cat pot, under the condition that $M_{\max}$ does not exceed $W$. Each pot must contain at least one cat.