Problem: Lollipops, Sweets and Chocolates II

Want to try solving this problem? You can submit your code online if you log in or register.

Lollipops, Sweets and Chocolates II

Input File: lscin.txt
Output File: lscout.txt
Time Limit: 1 second
Memory Limit: 1 GB

The grand opening of Lollipops, Sweets and Chocolates (LSC) was a great success! Since then a total of N LSC stores have opened along Australian Ice-cream and Oreo Crescent (AIOC), the most candilicious street in Sydney.

The street is divided into L blocks, spaced 1 metre apart. The blocks are labelled with numbers from 1 to L along the street, so that the distance between any two blocks a and b is |a - b| metres.

Each of the N stores occupies a different block. There are also M houses along the street, each occupying a different block. However, houses and stores may occupy the same block!

To keep the little boys and girls of Sydney excited about the stores, LSC has been distributing personalised pamphlets to the houses on the street. There is one pamphlet for each house. The ith pamphlet contains a message of the form:

There are s_i stores within walking distance of your house!

Wondering how far you have to walk to get your hands on another mouthwatering chlorosulfonic acid sorbet, you decide to investigate how far ‘walking distance’ could be. Walking distance means a distance of at most R metres, and you would like to determine a possible value for R. You know that the street is very long, so R cannot be greater than L.

You have collected all M pamphlets, but in your haste you have forgotten which house each pamphlet came from! Given all the numbers on the pamphlets, your task is to determine a possible value of R. LSC is notorious for distributing inaccurate pamphlets, so it is also possible that no such value of R exists.

Input

The first line of input will contain three integers N, M and L: the number of stores, the number of houses, and the length of the street, respectively.
The next line of input will contain N integers, describing the positions of the shops. These will be given in increasing order.
The next line of input will contain M integers, describing the positions of the houses. These will be given in increasing order.
The final line of input will contain M integers, describing the numbers on the pamphlets. These will be given in non-decreasing order. Note that this may not necessarily be the same order as the houses.

Output

Your program must output a single integer (whole number): a possible value of R, or −1 if no such value exists. If there are multiple possible answers, output any one of them. Note that the value of R must not be greater than L.

Sample Input 1

4 5 15
1 5 8 9
3 6 8 10 14
0 2 2 3 3

Sample Output 1

Sample Input 2

Sample Output 2

-1

Sample Input 3

Sample Output 3

Explanation

In the first sample input, it is possible that the pamphlets came from the houses in this order:

If R = 3, then:

The house at block 3 is within walking distance of 2 stores: the ones at blocks 1 and 5.
The house at block 6 is within walking distance of 3 stores: the ones at blocks 5, 8 and 9.
The house at block 8 is within walking distance of 3 stores: the ones at blocks 5, 8 and 9.
The house at block 10 is within walking distance of 2 stores: the ones at blocks 8 and 9.
The house at block 14 is within walking distance of no stores.

Note that 4 would also have been a correct output to this sample case.

In the second sample input, no matter which house each pamphlet came from, it is impossible to find a value of R that makes them correct.

In the third sample input, each house is within walking distance of exactly one store. The only value of R that satisfies this is 2.

Subtasks & Constraints

For all cases:

1 ≤ N, M ≤ 100,000.
1 ≤ L ≤ 1,000,000,000.
0 ≤ s_i ≤ N for all i.
All shops are located at distinct blocks between 1 and L, inclusive.
All houses are located at distinct blocks between 1 and L, inclusive.
A shop and a house may be located at the same block.

Furthermore:

For Subtask 1 (15 marks), s_i = 1 for all i. This means that each house is within walking of exactly one store. Sample Input 3 is an example of a case that could be in this subtask.
For Subtask 2 (15 marks), N, M ≤ 30.
For Subtask 3 (20 marks), N, M ≤ 300.
For Subtask 4 (20 marks), N, M ≤ 1000.
For Subtask 5 (30 marks), no further constraints apply.