E. Lighting the Street
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You've recently been promoted from an apprentice to a Junior City Planner.

Your first task in the new position is to figure out the optimal light bulb type the city should buy to place into the street lights on the side street Felseneggweg. You're not yet senior enough to decide on the light bulb type for the main road.

In this problem, the street is modeled as the segment $$$[0,L]$$$ of real numbers. All points on the segment must be illuminated (including its borders and non-integer points). There are $$$n$$$ street lights positioned on the street at integer positions $$$p_i$$$, each of which needs a new light bulb.

There are $$$m$$$ different light bulb types that illuminate varying distances, and their costs are determined by the distance they cover: the more the distance, the more expensive light bulbs of this type are. When installed in a position $$$x$$$, a light bulb of the $$$j$$$-th type illuminates the distance $$$l_j$$$ in each direction along the street. In other words, the whole segment $$$[x-l_j, x+l_j]$$$ is illuminated, including its border points.

Since the city would like to buy the light bulbs in bulk, all street lights must use the same light bulb type. You need to find the cheapest light bulb type that allows you to light the entirety of Felseneggweg to show your boss that your promotion was well deserved.

Input

The first line of input contains three integers $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$), and $$$L$$$ ($$$1 \leq L \leq 10^9$$$).

The second line contains $$$n$$$ integers $$$p_1,\dots,p_n$$$ ($$$0 \leq p_i \leq L$$$), the positions of the street lights. It is guaranteed that all positions are distinct.

The third line contains $$$m$$$ integers $$$l_1,\dots,l_m$$$ ($$$0 \leq l_j \leq L$$$), the illuminating distances of light bulb types. It is guaranteed that all distances are distinct.

Output

Return the optimal illuminating distance $$$l_j$$$, or $$$-1$$$ if it is not possible to cover the entire street.

Examples
Input
4 7 20
10 3 7 14
2 5 1 7 10 4 20
Output
7
Input
3 4 200
14 153 22
30 2 50 20
Output
-1