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

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.

- 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.

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.

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

3

3 2 6 1 3 5 2 6 1 3

-1

4 3 14 1 6 10 14 3 9 13 1 1 1

2

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.

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.

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.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 2 October 2022, 10:39am AEDT