There are three arrays a, b and c. Each of them consists of n integers. SmallY wants to find three integers u, v, w (0 ≤ u, v, w ≤ n) such that the following condition holds: each number that appears in the union of a, b and c, appears either in the first u elements of a, or in the first v elements of b, or in the first w elements of c. Of course, SmallY doesn't want to have huge numbers u, v and w, so she wants sum u + v + w to be as small as possible.

Please, help her to find the minimal possible sum of u + v + w.

Input

The first line contains a single integer n (1 ≤ n ≤ 105). The second line contains n space-separated integers a1, a2, ..., an — array a. The third line contains the description of array b in the same format. The fourth line contains the description of array c in the same format. The following constraint holds: 1 ≤ ai, bi, ci ≤ 109.

Output

Print a single integer — the minimum possible sum of u + v + w.

Examples

Input

3
1 1 101
1 2 1
3 2 1


Output

5

Input

5
1 1 2 2 3
2 2 4 3 3
3 3 1 1 1


Output

5

Note

In the first example you should choose u = 3, v = 0, w = 2. 

In the second example you should choose u = 1, v = 3, w = 1.
1
2
3
2
 8
190409007 190409007 352375776 190409007 352375776 352375776 352375776 352375776
190409007 190409007 190409007 190409007 190409007 352375776 352375776 190409007
190409007 352375776 352375776 190409007 190409007 190409007 352375776 352375776
 1
1
1
1
 1
377489979
588153796
588153796
 2
1 1
2 2
3 3
 4
1 1 1 1
1 1 1 1
1 1 1 1
 2
1 2
2 2
1 1
 3
1 1 2
1 1 3
1 1 4

2
 2
 1
 2
 3
 1
 2
 9

#include <bits/stdc++.h>
using namespace std;
int A, B, C;
long long d;
long long a[500006], b[100006], c[100006];
int main() {
  while (scanf("%I64d %d %d %d", &d, &A, &B, &C) != EOF) {
    long long ans = 0, sum, cnt;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= A; i++) {
      scanf("%I64d", &a[i]);
    }
    for (int i = 1; i <= B; i++) {
      scanf("%I64d", &b[i]);
    }
    for (int i = 1; i <= C; i++) {
      scanf("%I64d", &c[i]);
    }
    for (int i = 1; i <= A; i++) {
      if (i > 1 && a[i] == a[i - 1]) {
        ans += sum;
        continue;
      }
      sum = 0;
      for (int j = lower_bound(b + 1, b + B + 1, a[i] - d) - b;
           j <= upper_bound(b + 1, b + B + 1, a[i] + d) - b - 1; j++) {
        if (j > lower_bound(b + 1, b + B + 1, a[i] - d) - b &&
            b[j] == b[j - 1]) {
          sum += cnt;
          continue;
        }
        cnt = upper_bound(c + 1, c + C + 1, min(b[j] + d, a[i] + d)) -
              lower_bound(c + 1, c + C + 1, max(b[j] - d, a[i] - d));
        sum += cnt;
      }
      ans += sum;
    }
    printf("%I64d\n", ans);
  }
  return 0;
}
