Traffic

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Problem Description

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.

Input

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

Output

Print a non-negative integer denoting the minimum waiting time.

Sample Input

1 1
1
1
1 2
2
1 3

Sample Output

1
0

思路：

本题就是要将东西和南北的时间完全分开，让南北的等一定的时间然后开始行驶后无需等待也会相撞，所以就是将数据用数据存，然后找到一个cnt使得符合题意。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int n, m, k;
    while (scanf("%d %d", &n, &m) != EOF) {
        int a[10100] = {0}, b[10010] = {0};
        int maxn = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &k);
            a[k]++;
            maxn = max(maxn, k);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &k);
            b[k]++;
            maxn = max(maxn, k);
        }
        int cnt = 0;
        while (1) {
            int ans = 0;
            while (ans <= maxn) {
                if (!b[ans] || !a[ans + cnt]) ans++;
                else break;
            }
            if (ans == maxn + 1) {
                printf("%d\n", cnt);
                break;
            }
            cnt++;
        }
    }
    return 0;
}