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 = 200000;
int i, j, k, l, m, n, o, p, tot, root, a[N], b[N], len, h, L[N], lk[N], dl[N];
struct arr {
  int l, r, f, a, M, key, size, b;
} s[N];
inline int read() {
  int o = 0;
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') {
    o = o * 10 + c - '0';
    c = getchar();
  }
  return o;
}
inline void Init() {
  n = read();
  len = read();
  h = read();
  for (i = 1; i <= len; i++) b[i] = read();
  sort(b + 1, b + len + 1);
  for (i = 1; i <= n; i++) a[i] = read();
}
inline void put() {
  int i;
  printf("Begin root = %d\n", root);
  for (i = 1; i <= tot; i++)
    if (!dl[i]) {
      printf(
          "x = %d, f = %d, l = %d,r = %d,s[i].key = %d s[i].a = %d s[i].size = "
          "%d\n",
          i, s[i].f, s[i].l, s[i].r, s[i].key, s[i].a, s[i].size);
    }
  puts("end");
}
inline void update(int x) {
  s[x].M = s[x].a;
  if (s[x].l) s[x].M = min(s[x].M, s[s[x].l].M);
  if (s[x].r) s[x].M = min(s[x].M, s[s[x].r].M);
  s[x].size = s[s[x].l].size + s[s[x].r].size + 1;
}
inline void push(int x, int b) {
  if (x) {
    s[x].b += b;
    s[x].a += b;
    s[x].M += b;
  }
}
inline void zig(int x) {
  int y = s[x].f, ff = s[s[x].f].f;
  s[y].l = s[x].r;
  if (s[x].r) s[s[x].r].f = y;
  s[x].r = y;
  s[y].f = x;
  s[x].f = ff;
  if (s[ff].l == y)
    s[ff].l = x;
  else if (s[ff].r == y)
    s[ff].r = x;
  update(y);
}
inline void zag(int x) {
  int y = s[x].f, ff = s[s[x].f].f;
  s[y].r = s[x].l;
  if (s[x].l) s[s[x].l].f = y;
  s[x].l = y;
  s[y].f = x;
  s[x].f = ff;
  if (s[ff].l == y)
    s[ff].l = x;
  else if (s[ff].r == y)
    s[ff].r = x;
  update(y);
}
int path[N], cnt;
inline void splay(int x, int root) {
  int i, y, ff;
  y = x;
  cnt = 0;
  while (y) {
    path[++cnt] = y;
    y = s[y].f;
  }
  for (i = cnt; i >= 1; i--) {
    y = path[i];
    push(s[y].l, s[y].b);
    push(s[y].r, s[y].b);
    s[y].b = 0;
  }
  while (1) {
    y = s[x].f;
    if (y == root) {
      if (s[y].l == x)
        zig(x);
      else
        zag(x);
      break;
    }
    ff = s[y].f;
    if (s[ff].l == y) {
      if (s[y].l == x) {
        zig(y);
        zig(x);
      } else {
        zag(x);
        zig(x);
      }
    } else {
      if (s[y].l == x) {
        zig(x);
        zag(x);
      } else {
        zag(y);
        zag(x);
      }
    }
    if (ff == root) break;
  }
  update(x);
}
inline void insert(int i) {
  int now, l, r, next;
  now = root;
  tot++;
  s[tot].l = s[tot].r = 0;
  s[tot].key = a[i];
  s[tot].size = 1;
  s[tot].a = s[tot].M = 1 << 30;
  s[tot].b = 0;
  while (now != -1) {
    if (a[i] < s[now].key) {
      if (s[now].l)
        next = s[now].l;
      else {
        s[now].l = tot;
        s[tot].f = now;
        next = -1;
      }
    } else {
      if (s[now].r)
        next = s[now].r;
      else {
        s[now].r = tot;
        s[tot].f = now;
        next = -1;
      }
    }
    push(s[now].l, s[now].b);
    push(s[now].r, s[now].b);
    s[now].b = 0;
    now = next;
  }
  splay(tot, root);
  root = tot;
  lk[i] = root;
  s[root].a = L[i] - (s[root].size - s[s[root].r].size);
  push(s[root].r, -1);
  update(root);
}
inline void erase(int x) {
  dl[x] = 1;
  int now, next, o, p;
  splay(x, root);
  root = x;
  if (s[root].l && s[root].r) {
    push(s[root].r, 1);
    o = s[root].l;
    while (s[o].r) o = s[o].r;
    p = s[root].r;
    while (s[p].l) p = s[p].l;
    splay(o, root);
    root = o;
    splay(p, s[root].r);
    s[p].l = 0;
    update(p);
    update(root);
  } else {
    if (s[root].l) {
      root = s[root].l;
      s[root].f = 0;
    } else {
      push(s[root].r, 1);
      root = s[root].r;
      s[root].f = 0;
    }
  }
}
inline void Prepare() {
  int i, mid;
  for (i = 1; i <= n; i++) {
    o = 1;
    p = len;
    while (o <= p) {
      mid = o + p >> 1;
      if (a[i] + b[mid] >= h)
        p = mid - 1;
      else
        o = mid + 1;
    }
    L[i] = len - o + 1;
  }
  tot = 1;
  root = 1;
  s[1].l = s[1].r = s[1].f = 0;
  s[1].a = s[1].M = L[1] - 1;
  lk[1] = 1;
  s[1].key = a[1];
  s[1].size = 1;
  for (i = 2; i <= len; i++) insert(i);
}
inline void Solve() {
  int ans = 0, o, p, cul;
  for (i = 1; i <= n - len + 1; i++) {
    o = i;
    p = i + len - 1;
    cul = s[root].M;
    if (cul >= 0) ans++;
    if (p + 1 <= n) {
      erase(lk[o]);
      insert(p + 1);
    }
  }
  cout << ans << endl;
}
int main() {
  Init();
  Prepare();
  Solve();
  fclose(stdin);
  fclose(stdout);
  return 0;
}
