Cakey McCakeFace

Interview

Time limit7sMemory limit512 MB

Summary

Given sorted entry and exit timestamps, find the smallest nonnegative time difference d that maximizes how many entry times t satisfy t + d is an exit time.

Level: Medium5 of 10
Topics: Hash map, Array, Brute force, Implementation
Solved: No attempts yet

Problem

Cakey McCakeFace bakes its signature pastry, the Unknowable Cake, every day in a Paris facility. The cake succeeds or fails on one number, the cooking time, and that number is a closely guarded secret. Eve, a well known spy, wants to steal it, and your job is to help her.

Cakes are cooked in a single huge oven that has exactly one front door and one back door. Uncooked cakes go in through the front door. Once the exact secret cooking time has passed, a cake comes out through the back door. Only one cake can pass through the front door or the back door at any given moment.

Eve has secretly installed detectors at the front and the back of the oven. A detector records a signal every time a cake passes through its door. A cake that goes through the front door at time $t$ triggers the entry detector at $t$ , and it triggers the exit detector exactly cooking_time later when it goes through the back door. Every cake here is perfectly cooked.

After a few days Eve receives two sets of timestamps in milliseconds, one from each detector. The detectors are faulty: sometimes one fires when no cake passed, and sometimes one fails to fire when a cake did pass. Eve decided she can guess the secret cooking time well by finding the time difference that maximizes the number of correspondences between entry times and exit times. Compute that difference.

For a time difference $d$ , the number of correspondences is the number of recorded entry times $t$ such that $t + d$ is also recorded as an exit time.

Input

Line 1: the number $N$ of times the entry detector was triggered.
Line 2: the number $M$ of times the exit detector was triggered.
Line 3: the $N$ entry timestamps, in ascending order, with no repetition, separated by spaces.
Line 4: the $M$ exit timestamps, in ascending order, with no repetition, separated by spaces.

Limits

$1 \le N, M \le 2000$
every timestamp is an integer with $0 \le t \le 10^9$

Output

A single integer: the best guess of the secret cooking time, that is, the time difference $d \ge 0$ that maximizes the number of correspondences. If several time differences reach that maximum, print the smallest one. If no time difference produces a single correspondence, print 0.

Examples6

Example 1
Input
```
5
5
0 10 12 20 30
1 5 17 27 50
```
Expected output
```
5
```
Example 2
Input
```
1
1
0
0
```
Expected output
```
0
```
Example 3
Input
```
2
2
5 7
0 1
```
Expected output
```
0
```
Example 4
Input
```
2
4
0 1
2 3 5 6
```
Expected output
```
2
```
Example 5
Input
```
3
4
1 2 3
1 2 3 100
```
Expected output
```
0
```
Example 6
Input
```
1
1
0
1000000000
```
Expected output
```
1000000000
```