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

import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    static void removeFromArray(int[] arr, int val) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == val) {
                for (int j = i; j < arr.length - 1; j++) {
                    arr[j] = arr[j + 1];
                }
                break;
            }
        }
    }

    static void insertIntoArray(int[] arr, int val) {
        int cur = arr.length - 1;
        arr[cur] = val;
        while (cur > 0 && arr[cur] < arr[cur - 1]) {
            int tmp = arr[cur];
            arr[cur] = arr[cur - 1];
            arr[cur - 1] = tmp;
            --cur;
        }
    }

    static boolean good(int[] a, Integer[] b, int H) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            if (a[i] + b[n - i - 1] < H) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {

        int N, L, H, i;
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        L = in.nextInt();
        H = in.nextInt();
        Integer[] B = new Integer[L];
        for (i = 0; i < L; i++) {
            B[i] = in.nextInt();
        }
        int[] A = new int[N];
        for (i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }

        Arrays.sort(B);

        int[] sortedIndicesOfA = new int[N];
        int[] sortedValuesOfA = new int[N];
        {
            Long[] sortedA = new Long[N];
            for (i = 0; i < N; i++) {
                sortedA[i] = 1L * A[i] * N + i;
            }
            Arrays.sort(sortedA);
            for (i = 0; i < N; i++) {
                sortedValuesOfA[i] = (int) (sortedA[i] / N);
                sortedIndicesOfA[i] = (int) (sortedA[i] % N);
            }
        }

        int ans = 0;
        if (L <= 500) {
            int[] arr = new int[L];
            for (i = 0; i < L; i++) {
                arr[i] = A[i];
            }
            Arrays.sort(arr);
            ans += good(arr, B, H) ? 1 : 0;
            for (i = L; i < N; i++) {
                removeFromArray(arr, A[i - L]);
                insertIntoArray(arr, A[i]);
                ans += good(arr, B, H) ? 1 : 0;
            }
        } else {
            int Y = (int) Math.sqrt(1.0 * N);
            int X = L - Y;
            int[] listLeft = new int[L + 2];
            int[] listRight = new int[L + 2];
            int[] leftOver = new int[Y];
            for (int st = Y; st + X <= N; st += Y + 1) {
                for (i = 0; i <= L + 1; i++) {
                    listLeft[i] = i - 1;
                    listRight[i] = i + 1;
                }
                listRight[L + 1] = -1;
                int listCur = L + 1;

                boolean good = true;
                for (i = 0; i < N; i++) {
                    if (sortedIndicesOfA[i] >= st && sortedIndicesOfA[i] < st + X) {
                        int value = sortedValuesOfA[i];
                        if (listCur == L + 1) {
                            listCur = listLeft[listCur];
                        }
                        while (listCur > 0 && B[listCur - 1] + value >= H) {
                            listCur = listLeft[listCur];
                        }
                        listCur = listRight[listCur];
                        if (listCur == L + 1) {
                            good = false;
                            break;
                        }
                        if (listRight[listCur] != 0) {
                            listLeft[listRight[listCur]] = listLeft[listCur];
                        }
                        if (listLeft[listCur] != 0) {
                            listRight[listLeft[listCur]] = listRight[listCur];
                        }
                        listCur = listRight[listCur];
                    }
                }
                if (!good) {
                    continue;
                }

                for (i = st - Y; i < st; i++) {
                    leftOver[i - st + Y] = A[i];
                }
                Arrays.sort(leftOver);
                for (i = st - Y; i <= st && i + L <= N; i++) {
                    good = true;
                    listCur = listLeft[L + 1];
                    for (int j = 0; j < Y; j++, listCur = listLeft[listCur]) {
                        if (B[listCur - 1] + leftOver[j] < H) {
                            good = false;
                            break;
                        }
                    }
                    ans += good ? 1 : 0;

                    removeFromArray(leftOver, A[i]);
                    if (i + L < N) {
                        insertIntoArray(leftOver, A[i + L]);
                    }
                }
            }
        }

        System.out.println(ans);
    }
}