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, t[155555 * 5], ans = 0, o[155555], b[155555], a[155555],
                              add[5 * 155555];
inline void build(int l, int r, int i) {
  if (l == r) {
    t[i] = o[l];
    return;
  }
  int m = (l + r) / 2;
  build(l, m, i * 2);
  build(m + 1, r, i * 2 + 1);
  t[i] = ((t[i * 2]) > (t[i * 2 + 1]) ? (t[i * 2 + 1]) : (t[i * 2]));
}
inline void push(int i, int l, int r) {
  if (l != r) add[i * 2] += add[i], add[i * 2 + 1] += add[i];
  t[i] += add[i];
  add[i] = 0;
}
inline void upd(int l, int r, int ll, int rr, int v, int i) {
  if (ll > rr || ll < 1 || rr < 1 || ll > len || rr > len) return;
  push(i, l, r);
  if (l == ll && r == rr) {
    add[i] += v;
    push(i, l, r);
    return;
  }
  int m = (l + r) / 2;
  if (m >= rr)
    upd(l, m, ll, rr, v, i * 2);
  else if (ll > m)
    upd(m + 1, r, ll, rr, v, i * 2 + 1);
  else {
    upd(l, m, ll, m, v, i * 2);
    upd(m + 1, r, m + 1, rr, v, i * 2 + 1);
  }
  t[i] = ((t[i * 2] + add[i * 2]) > (t[i * 2 + 1] + add[i * 2 + 1])
              ? (t[i * 2 + 1] + add[i * 2 + 1])
              : (t[i * 2] + add[i * 2]));
}
inline void adde(int x, int v) {
  int k = lower_bound(b + 1, b + len + 1, h - x) - b;
  upd(1, len, k, len, v, 1);
}
int main(int argc, char* argv[]) {
  scanf("%d", &n);
  scanf("%d", &len);
  scanf("%d", &h);
  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]);
  for (int i = 1; i <= len; i++) o[i] = -i;
  build(1, len, 1);
  for (int i = 1; i <= len; i++) adde(a[i], 1);
  for (int i = len + 1; i <= n + 1; i++) {
    push(1, 1, len);
    if (t[1] >= 0) ans++;
    if (i == n + 1) break;
    adde(a[i], 1);
    adde(a[i - len], -1);
  }
  cout << ans << endl;
  return 0;
}
