You are playing a computer game, where you lead a party of m soldiers. Each soldier is characterised by his agility a_i.

The level you are trying to get through can be represented as a straight line segment from point 0 (where you and your squad is initially located) to point n + 1 (where the boss is located).

The level is filled with k traps. Each trap is represented by three numbers l_i, r_i and d_i. l_i is the location of the trap, and d_i is the danger level of the trap: whenever a soldier with agility lower than d_i steps on a trap (that is, moves to the point l_i), he gets instantly killed. Fortunately, you can disarm traps: if you move to the point r_i, you disarm this trap, and it no longer poses any danger to your soldiers. Traps don't affect you, only your soldiers.

You have t seconds to complete the level — that is, to bring some soldiers from your squad to the boss. Before the level starts, you choose which soldiers will be coming with you, and which soldiers won't be. After that, you have to bring all of the chosen soldiers to the boss. To do so, you may perform the following actions:

  * if your location is x, you may move to x + 1 or x - 1. This action consumes one second; 
  * if your location is x and the location of your squad is x, you may move to x + 1 or to x - 1 with your squad in one second. You may not perform this action if it puts some soldier in danger (i. e. the point your squad is moving into contains a non-disarmed trap with d_i greater than agility of some soldier from the squad). This action consumes one second; 
  * if your location is x and there is a trap i with r_i = x, you may disarm this trap. This action is done instantly (it consumes no time). 



Note that after each action both your coordinate and the coordinate of your squad should be integers.

You have to choose the maximum number of soldiers such that they all can be brought from the point 0 to the point n + 1 (where the boss waits) in no more than t seconds.

Input

The first line contains four integers m, n, k and t (1 ≤ m, n, k, t ≤ 2 ⋅ 10^5, n < t) — the number of soldiers, the number of integer points between the squad and the boss, the number of traps and the maximum number of seconds you may spend to bring the squad to the boss, respectively.

The second line contains m integers a_1, a_2, ..., a_m (1 ≤ a_i ≤ 2 ⋅ 10^5), where a_i is the agility of the i-th soldier.

Then k lines follow, containing the descriptions of traps. Each line contains three numbers l_i, r_i and d_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ d_i ≤ 2 ⋅ 10^5) — the location of the trap, the location where the trap can be disarmed, and its danger level, respectively.

Output

Print one integer — the maximum number of soldiers you may choose so that you may bring them all to the boss in no more than t seconds.

Example

Input


5 6 4 14
1 2 3 4 5
1 5 2
1 2 5
2 3 5
3 5 3


Output


3

Note

In the first example you may take soldiers with agility 3, 4 and 5 with you. The course of action is as follows:

  * go to 2 without your squad; 
  * disarm the trap 2; 
  * go to 3 without your squad; 
  * disartm the trap 3; 
  * go to 0 without your squad; 
  * go to 7 with your squad. 



The whole plan can be executed in 13 seconds.
import java.util.*;
import java.io.*;
import java.io.FileWriter; 

// Solution

public class Main 
{    
  public static void main (String[] argv) 
  {
	  new Main();
  } 
     
  
  boolean test = false;  
  final int[][] dirs8 = {{0,1}, {0,-1}, {-1,0}, {1,0}, {1,1},{1,-1},{-1,1},{-1,-1}};
  final int MOD = 998244353;//1000000007;  
  int n_bit = 1;
  int[] bit;
  
  public Main()   {
	FastReader in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
	
     
    //FastReader in = new FastReader(new BufferedReader(new FileReader("Main.in")));   
    
    //int nt = in.nextInt();    
    int nt = 1;
    StringBuilder sb = new StringBuilder();
    
    
    for (int it = 0; it < nt; it++) 
    {
       int nMan = in.nextInt();
       int xBoss = in.nextInt() + 1;
       int nTrap = in.nextInt();
       int time = in.nextInt();
       Integer[] mans = new Integer[nMan];
       for (int i = 0; i < nMan; i++) mans[i] = in.nextInt();
       Arrays.sort(mans, Collections.reverseOrder());
       
       int[][] traps = new int[nTrap][3];
       for (int i = 0; i < nTrap; i++)
       {
           traps[i][0] = in.nextInt();
           traps[i][1] = in.nextInt();
           traps[i][2] = in.nextInt();
       }
       //sort by location. small to big
       Arrays.sort(traps, (a,b)->(a[0]-b[0]));
       
       int lo = 0, hi = nMan - 1;
       while (lo <= hi)
       {
           int mid = (lo + hi) / 2;
           int health = mans[mid];
           if (f(nMan, xBoss, nTrap, time, traps, health))
           {
               lo = mid + 1;
           }else hi = mid - 1;
       }
       
       
       
       System.out.println(lo);
       //System.out.print(sb);
    }
    //System.out.print(sb);
  }
  
  private boolean f(int nMan, int xBoss, int nTrap, int time, int[][] traps, int health) {
      long cost=0;
      int xMan = 0;
      
      //System.out.println("min health = " + health);
      
      int hi = 0;
      for (int i = 0; i < nTrap; ){
          int[] trap = traps[i];
          int xtrap = trap[0], rt = trap[1], dt = trap[2];
          
          if (health >= dt) {
              // no need to handle trap
              i++;
              continue;
          }
          // need to handle it 
          //first move togother to xtrap - 1
          cost += xtrap - 1 - xMan;
          xMan = xtrap - 1;
          hi = rt;
          
          while (i < nTrap){
              if (traps[i][2] <= health) i++;
              else {
                  if (traps[i][0] > hi) break;                 
                  
                  hi = Math.max(hi, traps[i][1]);
                  i++;
              }
          }
          cost += 2 * (hi - xMan);
          
          //System.out.println("cost = " + cost + ", time = " + time + ", Exit");
          if (cost > time) return false;         
          
      }
      
      cost += xBoss - xMan;
      
      //System.out.println("cost = " + cost + ", time = " + time);
      return cost <= time;
  }
  
  private int[] build_z_function(String s)
  {
      int n = s.length();
      int[] zfun = new int[n];
      
      int l = -1, r = -1;
      for (int i = 1; i < n; i++)
      {
         // Set the start value
         if (i <= r)
            zfun[i] = Math.min(zfun[i-l], r - i + 1);
         
         while (i + zfun[i] < n && s.charAt(i + zfun[i]) == s.charAt(zfun[i])) 
             zfun[i]++;             
         
         if (i + zfun[i] - 1> r){
             l = i;
             r = i + zfun[i] - 1;
         }
      }
      
      if (test)
      {
          System.out.println("Z-function of " + s);
          for (int i = 0; i < n; i++) System.out.print(zfun[i] + " ");
          System.out.println();
      }
      return zfun;
  }
  
  private int query(int p)
  {
      int sum = 0;
      for (; p > 0; p -= (p & (-p)))
      {
          sum += bit[p];
      }
      return sum;
  }
  
  private void add(int p, int val)
  {
      //System.out.println("add to BIT " + p);
      for (; p <= n_bit; p += (p & (-p)))
      {
          bit[p] += val;
      }
  }
  
  
  
  private List<Integer> getMinFactor(int sum)
  {
      List<Integer>  factors = new ArrayList<>();
      
               for (int sz = 2; sz <= sum / sz; sz++){
                   if (sum % sz == 0) {
                       factors.add(sz);
                       factors.add(sum / sz);
                   }
               }
               if (factors.size() == 0)
                   factors.add(sum);
          
      return factors;
  }
  
  /* Tree class */
  class Tree {
      int V = 0;
      int root = 0;
      List<Integer>[] nbs;
      int[][] timeRange;
      int[] subTreeSize;
      int t;
      boolean dump = false;
      
      public Tree(int V, int root)
      {
          if (dump) 
              System.out.println("build tree with size = " + V + ", root = " + root); 
          
          this.V = V;          
          this.root = root;
          nbs = new List[V];
          subTreeSize = new int[V];
          for (int i = 0; i < V; i++)
              nbs[i] = new ArrayList<>();
          
              
      }
      
      public void doneInput()
      {
          dfsEuler();
      }
      
      public void addEdge(int p, int q)
      {
          nbs[p].add(q);
          nbs[q].add(p);
      }
      
      private void dfsEuler()
      {
          timeRange = new int[V][2];          
          t = 1;
          dfs(root);           
      }
      
      private void dfs(int node)
      {
          if (dump)
              System.out.println("dfs on node " + node + ", at time " + t);
          timeRange[node][0] = t;
          
          for (int next : nbs[node]) {
              if (timeRange[next][0] == 0)
              {
                  ++t;
                  dfs(next);                  
              }
          }
          timeRange[node][1] = t;
          subTreeSize[node] = t - timeRange[node][0] + 1;
      }
      
      public List<Integer> getNeighbors(int p) {
          return nbs[p];
      }
      
      public int[] getSubTreeSize(){
          return subTreeSize;
      }
      
      public int[][] getTimeRange()
      {
          if (dump){
              for (int i = 0; i < V; i++){
                  System.out.println(i + ": " + timeRange[i][0] + " - " + timeRange[i][1]);
              }
          }
          return timeRange;
      }
      
  }
  
  /* segment tree */
  class SegTree {
      long[] tree;
      long[] lazy;
      int n;
      boolean dump = false;
      
      public SegTree(int n)
      {
          if (dump)
              System.out.println("create segTree with size " + n);
          this.n = n;
          tree = new long[n*4];
          lazy = new long[n*4];
      }
      
      public SegTree(int n, int[] a) {
          this(n);
          buildTree(1, 0, n-1, a);
      }
      
      private void buildTree(int node, int lo, int hi, int[] a)
      {
          if (lo == hi) {
              tree[node] = a[lo];
              return;
          }
          
          int m = (lo + hi) / 2;
          buildTree(node * 2, lo, m, a);
          buildTree(node * 2 + 1, m + 1, hi, a);
          pushUp(node, lo, hi);
      }
      
      
      private void pushUp(int node, int lo, int hi)
      {
          if (lo >= hi) return;
          
          // add combine fcn
      }
      
      private void pushDown(int node, int lo, int hi)
      {
          if (lo > hi || lazy[node] == 0) return;
          
          tree[node] += lazy[node];
          tree[node] %= MOD;
          
          if (lo < hi) {              
              lazy[node * 2] += lazy[node];
              lazy[node * 2 + 1] += lazy[node];
              lazy[node * 2] %= MOD;
              lazy[node * 2 + 1] %= MOD;
          }
          
          lazy[node] = 0;
      }
      
      public void rangeUpdate(int fr, int to, long val)
      {
          if (dump)
              System.out.println("rangeUpdate : " + fr + " - " + to + " delta = " + val);
          rangeUpdate(1, 0, n-1, fr, to, val);
      }
      
      public long pointQuery(int p)
      {
          return pointQuery(1, 0, n-1, p);
      }
      
      
      private void rangeUpdate(int node, int lo, int hi, int fr, int to, long val)
      {
          if (dump)
              System.out.println("rangeUpdate : " + node + "[" + lo + " - " + hi + "]" + fr + " - " + to + " delta = " + val);
          
          pushDown(node, lo, hi);
          
          if (lo == fr && hi == to) {
              lazy[node] = val;              
              return;
          }
          
          int m = (lo + hi) / 2;
          if (to <=  m) 
              rangeUpdate(node * 2 , lo, m, fr, to, val);
          else if (fr > m)
              rangeUpdate(node * 2 + 1, m + 1, hi, fr, to, val);
          else {
              rangeUpdate(node * 2, lo, m, fr, m, val);
              rangeUpdate(node * 2 + 1, m + 1, hi, m + 1, to, val);
          }
          
          pushUp(node, lo, hi);          
      }
  
      /* pre-condition: lo <= p <= hi */
      private long pointQuery(int node, int lo, int hi, int p)
      {
          pushDown(node, lo, hi);
          
          if (lo == hi)
          {
              return tree[node];
          }
          
          int m = (lo + hi) / 2;
          if (p <= m) 
              return pointQuery(node * 2, lo, m, p);
          else
              return pointQuery(node * 2 + 1, m + 1, hi, p);
      }      
  
  }
  
  
  private long inv(long v)
  {
      return pow(v, MOD-2);
  }
  
  private long pow(long v, int p)
  {
      long ans = 1;
      while (p > 0)
      {
          if (p % 2 == 1)
              ans = ans * v % MOD;
          v = v * v % MOD;
          p = p / 2;
      }
      return ans;
  }
  
  private double dist(double x, double y, double xx, double yy)
  {
      return Math.sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
  }
  

  
 
  private int mod_add(int a, int b) {
      int v = a + b;
      if (v >= MOD) v -= MOD;
      return v;
  }
  
  
  private long overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
      if (x1 > x3) return overlap(x3, y3, x4, y4, x1, y1, x2, y2);
      
      if (x3 > x2 || y4 < y1 || y3 > y2) return 0L;
      
      //(x3, ?, x2, ?)
      int yL = Math.max(y1, y3);
      int yH = Math.min(y2, y4); 
      int xH = Math.min(x2, x4);
      
      return f(x3, yL, xH, yH);
  }
  //return #black cells in rectangle
  private long f(int x1, int y1, int x2, int y2) {
      long dx = 1L + x2 - x1;
      long dy = 1L + y2 - y1;
      if (dx % 2 == 0 || dy % 2 == 0 || (x1 + y1) % 2 == 0) 
          return 1L * dx * dy / 2;
      return 1L * dx * dy / 2 + 1;
  }
  
  private int distM(int x, int y, int xx, int yy) {
      return abs(x - xx) + abs(y - yy);
  }
  
  private boolean less(int x, int y, int xx, int yy) {
      return x < xx || y > yy;
  }
  
  private int mul(int x, int y) {
      return (int)(1L * x * y % MOD);
  }
  
  
 
  
  private int nBit1(int v) {
      int v0 = v;
      int c = 0;
      while (v != 0) {
          ++c;
          v = v & (v - 1);
      }
      return c;
  }
  
  private long abs(long v) {
      return v > 0 ? v : -v;
  }
  
  private int abs(int v) {
      return v > 0 ? v : -v;
  }
  
  private int common(int v) {
      int c = 0;
      while (v != 1) {
          v = (v >>> 1);
          ++c;
      }
      
      return c;
  }
  
  private void reverse(char[] a, int i, int j) {
      while (i < j) {
          swap(a, i++, j--);
      }
  }
  
  private void swap(char[] a, int i, int j) {
      char t = a[i];
      a[i] = a[j];
      a[j] = t;
  }
  
  private int gcd(int x, int y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private long gcd(long x, long y) {
      if (y == 0) return x;
      return gcd(y, x % y);
  }
  private int max(int a, int b) {
      return a >  b ? a : b;
  }
  
  private long max(long a, long b) {
      return a >  b ? a : b;
  }
  
  private int min(int a, int b) {
      return a >  b ? b : a;
  }
  
  private long min(long a, long b) {
      return a >  b ? b : a;
  }
  
  static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader(BufferedReader in)
        {            
            br = in;
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    String line = br.readLine();
                    if (line == null || line.length() == 0) return "";
                    st = new StringTokenizer(line);
                }
                catch (IOException  e)
                {
                    return "";
                    //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)
            {
                return null;
                //e.printStackTrace();
            }
            return str;
        }
    }
}