Manao is solving a problem with the following statement:

<image>

He came up with a solution that produces the correct answers but is too slow. You are given the pseudocode of his solution, where the function getAnswer calculates the answer to the problem:
    
    
      
    getAnswer(a[1..n], b[1..len], h)  
      answer = 0  
      for i = 1 to n-len+1  
        answer = answer + f(a[i..i+len-1], b, h, 1)  
      return answer  
      
    f(s[1..len], b[1..len], h, index)  
      if index = len+1 then  
        return 1  
      for i = 1 to len  
        if s[index] + b[i] >= h  
          mem = b[i]  
          b[i] = 0  
          res = f(s, b, h, index + 1)  
          b[i] = mem  
          if res > 0  
            return 1  
      return 0  
    

Your task is to help Manao optimize his algorithm.

Input

The first line contains space-separated integers n, len and h (1 ≤ len ≤ n ≤ 150000; 1 ≤ h ≤ 109). The second line contains len space-separated integers b1, b2, ..., blen (1 ≤ bi ≤ 109). The third line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print a single number — the answer to Manao's problem.

Examples

Input

5 2 10
5 3
1 8 5 5 7


Output

2
#include <bits/stdc++.h>
using namespace std;
int n, len, h, X, Y, ans = 0;
int *a, *b, *c, *d, *B, *R;
bool use[155555];
pair<int, int> aa[155555];
inline void er(int *&a, int v, int n) {
  int k = 0, j = 1000000000;
  for (int i = 1; i <= n; i++)
    if (a[i] < v)
      R[++k] = a[i];
    else {
      j = i;
      break;
    }
  for (int i = j + 1; i <= n; i++) R[++k] = a[i];
  for (int i = 1; i <= n - 1; i++) a[i] = R[i];
}
inline void ins(int *&a, int v, int n) {
  int k = 0, j = 1000000000;
  for (int i = 1; i <= n; i++)
    if (a[i] <= v)
      R[++k] = a[i];
    else {
      j = i;
      break;
    }
  R[++k] = v;
  for (int i = j; i <= n; i++) R[++k] = a[i];
  for (int i = 1; i <= n + 1; i++) a[i] = R[i];
}
inline int Brute() {
  int ret = 0;
  reverse(b + 1, b + len + 1);
  for (int i = 1; i <= len; i++) c[i] = a[i];
  sort(c + 1, c + len + 1);
  for (int i = 1; i <= n - len + 1; i++) {
    bool ok = true;
    for (int j = 1; j <= len; j++)
      if (c[j] + b[j] < h) {
        ok = false;
        break;
      }
    if (ok) ret++;
    er(c, a[i], len);
    ins(c, a[i + len], len - 1);
  }
  return ret;
}
inline int solve(int i) {
  if (n - i + 1 < len) return 0;
  memset(use, 0, sizeof(use));
  int l = i + Y, r = i + Y + X - 1, k = 0, ret = 0;
  for (int j = 1; j <= n; j++)
    if (aa[j].second >= l && aa[j].second <= r) c[++k] = aa[j].first;
  reverse(c + 1, c + k + 1);
  int rr = 1;
  for (int ll = 1; ll <= k; ll++) {
    while (rr <= len && c[ll] + b[rr] < h) rr++;
    if (rr > len) return 0;
    use[rr] = true;
    rr++;
  }
  int cp = 0, t = 0;
  for (int j = 1; j <= len; j++)
    if (!use[j]) B[++cp] = b[j];
  reverse(B + 1, B + cp + 1);
  for (int j = i; j <= i + Y - 1; j++) d[++t] = a[j];
  sort(d + 1, d + t + 1);
  for (int j = i; j <= i + Y - 1; j++) {
    if (j + len - 1 > n) break;
    bool ok = true;
    for (int q = 1; q <= Y; q++)
      if (B[q] + d[q] < h) {
        ok = false;
        break;
      }
    if (ok) ret++;
    er(d, a[j], Y);
    ins(d, a[j + len], Y - 1);
  }
  return ret;
}
int main(int argc, char *argv[]) {
  scanf("%d", &n);
  scanf("%d", &len);
  scanf("%d", &h);
  a = new int[n + 111];
  b = new int[n + 111];
  c = new int[n + 111];
  d = new int[n + 111];
  B = new int[n + 111];
  R = new int[n + 111];
  for (int i = 1; i <= len; i++) scanf("%d", &b[i]);
  sort(b + 1, b + len + 1);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), aa[i] = make_pair(a[i], i);
  sort(aa + 1, aa + n + 1);
  if (len <= 400) {
    cout << Brute() << endl;
    return 0;
  }
  Y = sqrt(n);
  X = len - Y;
  for (int i = 1; i <= n; i += Y) ans += solve(i);
  cout << ans << endl;
  return 0;
}
