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.io.*;
import java.util.*;
@SuppressWarnings("unchecked")
public class E338 
{
   static long time = System.currentTimeMillis();
   static int[] min;
   static int[] lazy;
   public static void main(String[] args) throws Exception 
   {
      FastReader infile = new FastReader();
      //infile = new FastReader("text.in");
      int n = infile.nextInt();
      int len = infile.nextInt();
      int h = infile.nextInt();
      int[] a = new int[n+1];
      double[] b = new double[len+1];
      for(int x = 1; x <= len; x++)
         b[x] = infile.nextInt();
      Arrays.sort(b);
      for(int x = 1; x <= n; x++)
         a[x] = infile.nextInt();
      int ans = 0;
      int index = 1;
      HashMap<Integer, Integer> left = new HashMap<Integer, Integer>();
      HashMap<Integer, Integer> right = new HashMap<Integer, Integer>();
      ArrayList<Double> list = new ArrayList<Double>();
      list.add(0.0);
      int prev = 1;
      for(int x = 2; x <= len; x++)
      {
         if(b[prev]!=b[x])
         {
            list.add(b[prev]);
            left.put((int)b[prev], prev);
            right.put((int)b[prev], x-1);
            prev = x;
         }   
      }
      if(left.get(b[prev])==null)
      {
         list.add(b[prev]);
         left.put((int)b[prev], prev);
         right.put((int)b[prev], len);
      }   
      int size = left.size();
      min = new int[4*size+1];
      lazy = new int[4*size+1];
      for(int x = 1; x <= size; x++)
      {
         int val = (int) (double) list.get(x);
         update(1, 1, size, x, x, -right.get(val));
      }
      for(int x = 1; x <= len; x++)
      {
         //System.out.println(Math.max(h-a[x], 0)-0.5);
         update(1, 1, size, -Collections.binarySearch(list, Math.max(h-a[x], 0)-0.5)-1, size, 1);
      }
      for(int x = len; x <= n; x++)
      {
         if(query(1, 1, size, 1, size, 0)>=0)
            ans++;
         if(x==n)
            break;
         update(1, 1, size, -Collections.binarySearch(list, Math.max(h-a[x-len+1], 0)-0.5)-1, size, -1);
         update(1, 1, size, -Collections.binarySearch(list, Math.max(h-a[x+1], 0)-0.5)-1, size, 1);
      }
      StringBuilder sb = new StringBuilder();
      sb.append(ans);
      System.out.println(sb);
      //System.out.println("Time: "+(System.currentTimeMillis()-time));
   }
   public static void update(int pos, int left, int right, int ltar, int rtar, int val)
   {
      if(ltar>rtar)
         return;
      if(rtar<left||right<ltar)
         return;
      if(ltar<=left&&right<=rtar)
      {
         lazy[pos]+=val;
         return;
      }
      int mid = (left+right)/2;
      update(2*pos, left, mid, ltar, rtar, val);
      update(2*pos+1, mid+1, right, ltar, rtar, val);
      min[pos] = Math.min(min[2*pos]+lazy[2*pos], min[2*pos+1]+lazy[2*pos+1]);
   }
   public static int query(int pos, int left, int right, int ltar, int rtar, int push)
   {
      return lazy[pos]+min[pos];
   }
}
class FastReader
{
   BufferedReader br;
   StringTokenizer st;

   public FastReader(String file) throws FileNotFoundException
   {
      br = new BufferedReader(new FileReader(file));
   }
   
   public FastReader() throws FileNotFoundException
   {
      br = new BufferedReader(new InputStreamReader(System.in));
   }
 
   String next()
   {
      while (st == null || !st.hasMoreElements())
      {
         try
         {
            st = new StringTokenizer(br.readLine());
         }
         catch (IOException  e)
         {
            e.printStackTrace();
         }
      }
      return st.nextToken();
   }
 
   int nextInt()
   {
      return Integer.parseInt(next());
   }
 
   long nextLong()
   {
      return Long.parseLong(next());
   }
 
   double nextDouble()
   {
      return Double.parseDouble(next());
   }
 
   String nextLine()
   {
      String str = "";
      try
      {
         str = br.readLine();
      }
      catch (IOException e)
      {
         e.printStackTrace();
      }
      return str;
   }
}