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
//package codeforces;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Optimize {

    private static void preCompute(int[] segmentArr, int len, int l, int r, int i) { // 1 based segmentArr
        if (l == r) segmentArr[i] = len - l;
        else {
            int m = (l + r) >>> 1;
            preCompute(segmentArr, len, l, m, i << 1);
            preCompute(segmentArr, len, m + 1, r, (i << 1) | 1);

            segmentArr[i] = Math.min(segmentArr[i << 1], segmentArr[(i << 1) | 1]);
        }
    }

    private static void updateWithAmount(int[] segmentArr, int[] lazy, int findl, int findr, int amount, int l, int r, int i) {
        if (r < findl || findr < l) {
            // out of range
        } else {

            if (findl <= l && r <= findr) {
                segmentArr[i] += amount;
                lazy[i] += amount;

                return; // don't go any further boy!
            }

            if (lazy[i] != 0) { // lazy set => children needs to be updated
                lazy[i << 1] += lazy[i];
                segmentArr[i << 1] += lazy[i];

                lazy[(i << 1) | 1] += lazy[i];
                segmentArr[(i << 1) | 1] += lazy[i];

                lazy[i] = 0;
            }

            int m = (l + r) >>> 1;
            updateWithAmount(segmentArr, lazy, findl, findr, amount, m + 1, r, (i << 1) | 1);
            updateWithAmount(segmentArr, lazy, findl, findr, amount, l, m, i << 1);

            segmentArr[i] = Math.min(segmentArr[i << 1], segmentArr[(i << 1) | 1]);
        }
    }

    public static void main(String[] args) throws Exception {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()), len = Integer.parseInt(st.nextToken()), h = Integer.parseInt(st.nextToken());

        int[] a = new int[n], b = new int[len];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < len; i++) b[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(b);

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());

        int[] segmentArr = new int[4 * len], lazy = new int[4 * len];
        preCompute(segmentArr, len, 0, len - 1, 1);

        int result = 0;
        int[] index = new int[n]; // save indexes of elements used in array b for each element fo a

        for (int i = 0, negativeOnesCount = 0; i < n; i++) {
            int key = h - a[i]; // now find index of element >= key in array b, lowerBound

            index[i] = -1;
            if (key <= b[len - 1]) {
                int l = 0, r = len - 1;
                while (l < r) { // 5 7
                    int mid = (l + r) >>> 1;
                    if (key <= b[mid])
                        r = mid;
                    else // key > b[mid]
                        l = mid + 1;
                }
                index[i] = r;
            }

            if (index[i] != -1)
                updateWithAmount(segmentArr, lazy, 0, index[i], -1, 0, len - 1, 1);
            else
                negativeOnesCount++;

            if (i >= len)
                if (index[i - len] != -1)
                    updateWithAmount(segmentArr, lazy, 0, index[i - len], 1, 0, len - 1, 1);
                else
                    negativeOnesCount--;


            if (i >= len - 1 && negativeOnesCount == 0 && segmentArr[1] >= 0)
                result++;
        }

        System.out.println(result);
    }
}
