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;
const int N = 2e5;
int tr;
struct treap {
  int lt, rt, dt, pri, sz;
  int vl, lz, mn;
} bst[N + 2];
void tooLazy(int nd) {
  if (nd == 0) return;
  int x = bst[nd].lz, l = bst[nd].lt, r = bst[nd].rt;
  bst[nd].vl += x;
  bst[nd].mn += x;
  if (l) bst[l].lz += x;
  if (r) bst[r].lz += x;
  bst[nd].lz = 0;
}
void cal(int nd) {
  tooLazy(nd);
  int l = bst[nd].lt, r = bst[nd].rt;
  bst[nd].sz = bst[l].sz + bst[r].sz + 1;
  bst[nd].mn = min({bst[nd].vl, bst[l].mn, bst[r].mn});
}
pair<int, int> splitbyValue(int nd, int vl) {
  tooLazy(nd);
  tooLazy(bst[nd].lt);
  tooLazy(bst[nd].rt);
  if (!nd) return {0, 0};
  pair<int, int> p;
  if (bst[nd].dt <= vl) {
    p = splitbyValue(bst[nd].rt, vl);
    bst[nd].rt = p.first;
    cal(nd);
    return {nd, p.second};
  } else {
    p = splitbyValue(bst[nd].lt, vl);
    bst[nd].lt = p.second;
    cal(nd);
    return {p.first, nd};
  }
}
pair<int, int> splitbySize(int nd, int ss) {
  tooLazy(nd);
  tooLazy(bst[nd].lt);
  tooLazy(bst[nd].rt);
  if (!nd) return {0, 0};
  pair<int, int> p;
  if (bst[bst[nd].lt].sz >= ss) {
    p = splitbySize(bst[nd].lt, ss);
    bst[nd].lt = p.second;
    cal(nd);
    return {p.first, nd};
  } else {
    p = splitbySize(bst[nd].rt, ss - bst[bst[nd].lt].sz - 1);
    bst[nd].rt = p.first;
    cal(nd);
    return {nd, p.second};
  }
}
int join(int lt, int rt) {
  tooLazy(lt);
  tooLazy(bst[lt].lt);
  tooLazy(bst[lt].rt);
  tooLazy(rt);
  tooLazy(bst[rt].lt);
  tooLazy(bst[rt].rt);
  if (!lt) return rt;
  if (!rt) return lt;
  if (bst[lt].pri >= bst[rt].pri) {
    bst[lt].rt = join(bst[lt].rt, rt);
    cal(lt);
    return lt;
  } else {
    bst[rt].lt = join(lt, bst[rt].lt);
    cal(rt);
    return rt;
  }
}
int a[N + 2], b[N + 2], mx[N + 2];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, len, h;
  cin >> n >> len >> h;
  for (int i = 1; i <= len; i++) cin >> b[i];
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(b + 1, b + len + 1, greater<int>());
  int root = 0;
  bst[0].mn = 1e9;
  for (int i = 1; i <= n; i++) {
    int lo = 1, hi = len + 1, md;
    while (lo < hi) {
      md = (lo + hi) / 2;
      if (a[i] + b[md] < h)
        hi = md;
      else
        lo = md + 1;
    }
    mx[i] = lo - 1;
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    pair<int, int> p = splitbyValue(root, a[i] - 1);
    bst[p.second].lz--;
    tooLazy(p.second);
    int dt = mx[i] - 1 - bst[p.first].sz;
    bst[++tr] = {0, 0, a[i], rand(), 1, dt, 0, dt};
    root = join(p.first, tr);
    root = join(root, p.second);
    if (i > len) {
      int dl = a[i - len];
      p = splitbyValue(root, dl - 1);
      pair<int, int> p2 = splitbySize(p.second, 1);
      bst[p2.second].lz++;
      tooLazy(p2.second);
      root = join(p.first, p2.second);
    }
    if (i >= len && bst[root].mn >= 0) ans++;
  }
  cout << ans << endl;
  return 0;
}
