Optimize!

Manao is solving a problem with the following statement:

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 ≤ 10⁹). The second line contains len space-separated integers b ₁, b ₂, …, b _len (1 ≤ b _i ≤ 10⁹). The third line contains n space-separated integers a ₁, a ₂, …, a _n (1 ≤ a _i ≤ 10⁹).

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

Solution:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>

using namespace std;

const int N = 2000010;

int mx[N], add[N], a[N], b[N];

void modify(int x, int l, int r, int ll, int rr, int v) {
if (l > rr || ll > r) return;
if (l >= ll && r <= rr) {
    add[x] += v;
    return;
  }
  if (add[x] != 0) {
    add[x + x] += add[x];
    add[x + x + 1] += add[x];
    add[x] = 0;
  }
  int y = (l + r) >> 1;
modify(x + x, l, y, ll, rr, v);
modify(x + x + 1, y + 1, r, ll, rr, v);
mx[x] = mx[x + x + 1] + add[x + x + 1];
if (mx[x + x] + add[x + x] > mx[x]) mx[x] = mx[x + x] + add[x + x];
}

int main() {
int n, len, h;
scanf("%d %d %d", &n, &len, &h);
for (int i=1;i<=len;i++) scanf("%d", b+i);
  sort(b + 1, b + len + 1);
  reverse(b + 1, b + len + 1);
  for (int i=1;i<=n;i++) {
    int foo;
    scanf("%d", &foo);
    int ll = 0, rr = len;
    while (ll < rr) {
      int mid = (ll + rr + 1) >> 1;
if (foo + b[mid] >= h) ll = mid;
else rr = mid - 1;
}
a[i] = ll;
}
memset(mx, 0, sizeof(mx));
memset(add, 0, sizeof(add));
for (int i=1;i<=len;i++) modify(1, 0, len, i, i, -i);
  for (int i=1;i<=len-1;i++) modify(1, 0, len, a[i], len, 1);
  int ans = 0;
  for (int i=len;i<=n;i++) {
    modify(1, 0, len, a[i], len, 1);
    if (mx[1] + add[1] == 0) ans++;
    modify(1, 0, len, a[i - len + 1], len, -1);
  }
  printf("%d\n", ans);
  return 0;
}