Avin is observing the cars at a crossroads. He finds that there are n cars running in the east-west direction with the i-th car passing the intersection at time ai . There are another m cars running in the north-south direction with the i-th car passing the intersection at time bi . If two cars passing the intersections at the same time, a traffic crash occurs. In order to achieve world peace and harmony, all the cars running in the north-south direction wait the same amount of integral time so that no two cars bump. You are asked the minimum waiting time.
The first line contains two integers n and m (1 ≤ n, m ≤ 1, 000). The second line contains n distinct integers ai (1 ≤ ai ≤ 1, 000). The third line contains m distinct integers bi (1 ≤ bi ≤ 1, 000).
Print a non-negative integer denoting the minimum waiting time.
1 | 1 1 |
1 | 1 |
There is a fuzzy point in the description. That is all the car has to wait the same amount of time. For example:
dir\min | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
east-west | 1 | 3 | 4 | |||
north-south | 1 | 2 | 5 |
The north-south cars has a car go through minute 1 and is conflict with the east-west car. So it has to wait a minute. But all the cars has to wait the same amount of time. So the situation looks like this:
dir\min | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
east-west | 1 | 3 | 4 | |||
north-south | 2 | 3 | 6 |
However there is still a confliction at minute 3. So wait another minute.
dir\min | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
east-west | 1 | 3 | 4 | ||||
north-south | 3 | 4 | 7 |
Now there are two conflictions. We keep waiting another minute.
dir\min | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
east-west | 1 | 3 | 4 | |||||
north-south | 4 | 5 | 8 |
Ah—!Another minute.
dir\min | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
east-west | 1 | 3 | 4 | ||||||
north-south | 5 | 6 | 9 |
Finally, all the cars can pass without confliction.
The code is to stimulate this process to find the least waiting minute.
1 |
|