The New Kid

View as PDF

Submit solution


Points: 5
Time limit: 2.0s
Memory limit: 64M

Authors:
Problem type

Jagdeep is moving into a neighbourhood near Massey. Since Jagdeep is such a popular kid, he already knows every single person on the street he is looking to move to. There are N houses that are empty (1 \le N \le 1\,000), but there are also M houses with people in them who he doesn't like (1 \le M \le 3\,000). Each house is up to 1\,000\,000\,000 meters away from the front of the street, and each house is on the street. What is the position of the empty house that is the farthest away from the M houses with people in them who Jagdeep doesn't like?

Input Specification

The first line contains two integers, N and M, separated by a space. On each of the next N lines, there is a single non-negative integer denoting the position of an empty house. On each of the next M lines, there is a single non-negative integer denoting the position of a house with people in them who Jagdeep doesn't like.

Output Specification

The position of the empty house that is the farthest away from the M houses with people in them who Jagdeep doesn't like. If there are multiple empty houses that tie for farthest distance, output the one closest to the front of the street.

Sample Input

3 5
3
24
18
2
23
7
14
25

Sample Output

18

Explanation for Sample Output

There are empty houses at 3, 24, and 18. The first empty house is closest to 2, so its distance is |3-2| = 1. The second empty house is closest to 23 or 25, so its distance is 1. The third empty house is closest to 14, so its distance is 4. The answer is the position of the third empty house, which is 18.


Comments

There are no comments at the moment.