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 \le m, n, k, t \le 2 \cdot 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 \le a_i \le 2 \cdot 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 \le l_i \le r_i \le n$, $1 \le d_i \le 2 \cdot 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.

Difficulty: interview

Starter code:

Solutions:

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

M,N,K,T = inpl()
AA = inpl()

DD_di = []
LR = []
for i in range(K):
    L,R,D = inpl()
    LR.append((L,R))
    DD_di.append((D,i))

DD_di.sort()
DD_d = [D for D,i in DD_di]

def solve(x):
    idx = bisect.bisect_right(DD_d, x)
    path = [0]*(N+2)
    for D,i in DD_di[idx:]:
        L,R = LR[i]
        path[L] += 1
        path[R+1] -= 1

    t = N+1
    bp = path[0]
    for i in range(1,N+2):
        p = bp + path[i]
        if p > 0:
            t += 2
        bp = p

    return t <= T


OK = (10**5) * 2 + 10
NG = -1

while OK-NG > 1:
    mid = (OK+NG)//2
    if solve(mid):
        OK = mid
    else:
        NG = mid

ans = 0
for A in AA:
    if A >= OK:
        ans += 1

print(ans)


import sys
input = lambda: sys.stdin.readline().rstrip()

def chk(a):
    Y = [0] * (N + 10)
    for l, r, d in X:
        if d <= a: continue
        Y[l-1] += 1
        Y[r] -= 1
    for i in range(1, N+10):
        Y[i] += Y[i-1]
    return 1 if sum([min(Y[i], 1) for i in range(N+5)]) * 2 + N+1 <= T else 0

M, N, K, T = list(map(int, input().split()))
A = [int(a) for a in input().split()]
X = []
for _ in range(K):
    l, r, d = list(map(int, input().split()))
    X.append((l, r, d))

l, r = 0, 2*10**5
while r - l > 1:
    m = (l+r) // 2
    if chk(m):
        r = m
    else:
        l = m

print(len([a for a in A if a >= r]))



#!/usr/bin/env python3
import sys
input = sys.stdin.readline

sol_n, n, trap_n, t = [int(item) for item in input().split()]
sold = [int(item) for item in input().split()]
sold.sort(reverse=True)
trap = []
for i in range(trap_n):
    l, r, d = [int(item) for item in input().split()]
    trap.append((d, l, r))
trap.sort()
ll = 0; rr = sol_n + 1
while rr - ll > 1:
    mid = (ll + rr) // 2
    to_save = sold[mid - 1]
    alone_walk = [0] * (n + 1)
    for d, l, r in trap:
        if d > to_save:
            alone_walk[l-1] += 1
            alone_walk[r] -= 1
    total = 0
    time = 0
    for item in alone_walk:
        total += item
        if total > 0:
            time += 2
    time += n + 1
    if time <= t:
        ll = mid
    else:
        rr = mid
print(ll)

3

import os
import sys


def main():
    M, N, K, T = read_ints()
    A = read_ints()
    B = [tuple(read_ints()) for _ in range(K)]
    print(solve(M, N, K, T, A, B))


def solve(M, N, K, T, A, B):
    B.sort()

    def seconds(agi):
        traps = [(l, r) for l, r, d in B if d > agi]
        x = 0
        sec = 0
        sw = -1
        for l, r in traps:
            if sw != -1 and sw < l:
                sec += 2 * (sw - x)
                sw = -1

            if sw != -1:
                sw = max(sw, r)
                continue

            sec += l - 1 - x
            x = l - 1
            sw = r

        if sw != -1:
            sec += 2 * (sw - x)

        sec += N + 1 - x
        return sec

    min_agi = min(A)
    max_agi = max(A)

    if seconds(max_agi) > T:
        return 0
    if seconds(min_agi) <= T:
        return len(A)

    lb = min_agi
    ub = max_agi
    while ub - lb > 1:
        agi = (lb + ub) // 2
        if seconds(agi) > T:
            lb = agi
        else:
            ub = agi

    return len([a for a in A if a >= ub])


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def __starting_point():
    main()

__starting_point()

def inter(a,b):
    if b[0]<=a[1]:
        return 1
    return 0
def check(le):
    if le==0:
        return 1
    mi=it[le-1]
  #  print(mi)
    tr=[i[:2] for i in aaa if i[2]>mi]
    if tr==[]:
        return 1
    aa=[tr[0][:]]
  #  print(le,tr)
    for i in range(1,len(tr)):
        if inter(aa[-1],tr[i]):
            aa[-1][1]=max(aa[-1][1],tr[i][1])
        else:
            aa.append(tr[i][:])
    tt=0
    a=0
   # print(aa)
    for i in range(len(aa)):
        tt+=(aa[i][0]-1-a)
        a=aa[i][0]-1
        tt+=3*(aa[i][1]-aa[i][0]+1)
        a=aa[i][1]
    tt+=(n+1)-a
  #  print(le,tt)
  #  print()
    return tt<=t
    
m,n,k,t=list(map(int,input().split()))
it=list(map(int,input().split()))
it.sort(reverse=True)
aaa=[]
for i in range(k):
    l,r,d=list(map(int,input().split()))
    aaa.append([l,r,d])
aaa.sort()
low=0
high=m
while low<high-1:
    mid=(low+high)//2
    a=check(mid)
    if a:
        low=mid
    else:
        high=mid-1
for i in range(high,low-1,-1):
    if check(i):
        ans=i
        break
print(ans)


import sys
input=sys.stdin.readline
def inter(a,b):
    if b[0]<=a[1]:
        return 1
    return 0
def check(le):
    if le==0:
        return 1
    mi=it[le-1]
  #  print(mi)
    tr=[i[:2] for i in aaa if i[2]>mi]
    if tr==[]:
        return 1
    aa=[tr[0][:]]
  #  print(le,tr)
    for i in range(1,len(tr)):
        if inter(aa[-1],tr[i]):
            aa[-1][1]=max(aa[-1][1],tr[i][1])
        else:
            aa.append(tr[i][:])
    tt=0
    a=0
   # print(aa)
    for i in range(len(aa)):
        tt+=(aa[i][0]-1-a)
        a=aa[i][0]-1
        tt+=3*(aa[i][1]-aa[i][0]+1)
        a=aa[i][1]
    tt+=(n+1)-a
  #  print(le,tt)
  #  print()
    return tt<=t
    
m,n,k,t=list(map(int,input().split()))
it=list(map(int,input().split()))
it.sort(reverse=True)
aaa=[]
for i in range(k):
    l,r,d=list(map(int,input().split()))
    aaa.append([l,r,d])
aaa.sort()
low=0
high=m
while low<high-1:
    mid=(low+high)//2
    a=check(mid)
    if a:
        low=mid
    else:
        high=mid-1
for i in range(high,low-1,-1):
    if check(i):
        ans=i
        break
print(ans)


import sys
from bisect import bisect_left
m, n, k, t = map(int, input().split())
a = sorted(map(int, input().split()))
traps = sorted(list(map(int, l.split())) for l in sys.stdin)

ok, ng = 2*10**5, 0
while ok - ng > 1:
    mid = (ok+ng) // 2
    l, r = 0, 0
    dist = n + 1
    for i in range(k):
        if mid < traps[i][2]:
            if r < traps[i][0]:
                dist += (r - l) * 2
                l, r = traps[i][0]-1, traps[i][1]
            else:
                r = max(r, traps[i][1])

    dist += (r - l) * 2

    if dist <= t:
        ok = mid
    else:
        ng = mid

print(m - bisect_left(a, ok))

m,n,k,t = list(map(int,input().split()))
a = [0] + sorted(list(map(int,input().split()))) + [3*10**5]
data = sorted([list(map(int,input().split())) for _ in range(k)])
#print(data)

ok = m+1
ng = 0

while ok-ng > 1:
    mid = (ok + ng)//2
    A = a[mid]

    interval_set = []
    for i in range(k):
        if data[i][2]<= A:
            continue
        if len(interval_set)==0:
            interval_set.append([data[i][0],data[i][1]])
        else:
            if interval_set[-1][1] < data[i][0]:
                interval_set.append([data[i][0],data[i][1]])
            elif interval_set[-1][1] < data[i][1]:
                new_interval = [interval_set.pop()[0],data[i][1]]
                interval_set.append(new_interval)
    time = n+1
    for interval in interval_set:
        time += (interval[1]-interval[0]+1)*2

    #print(mid,A, interval_set,time)
    if time <= t:
        ok = mid
    else:
        ng = mid

print(m-ok+1)
#print(a[ok])


m, n, k, t = [int(s) for s in input().split()]
A = [int(s) for s in input().split()]
A.sort()
traps = []
for i in range(k):
    l, r, d = [int(s) for s in input().split()]
    traps.append((l,r,d))
traps.sort()

def canTake(agi):
    farest = 0
    trapIndex = 0
    wasteTime = 0
    while trapIndex < len(traps):
        trap = traps[trapIndex]
        if trap[2] <= agi:
            trapIndex += 1
            continue
        if trap[1] <= farest:
            trapIndex += 1
            continue
        # r > farest
        newFarest = trap[1]
        if trap[0] > farest:
            wasteTime += (trap[1] - trap[0] + 1)*2
        else:
            wasteTime += (newFarest - farest)*2
        farest = newFarest
        trapIndex += 1

    if wasteTime + n + 1 > t:
        return False
    else:
        return True

def binSearch(A):
    if canTake(A[0]):
        return 0
    low = 0  # imposs tank
    high = len(A)  # poss tank
    while high-low > 1:
        mid = (low+high)//2
        if canTake(A[mid]):
            high = mid
        else:
            low = mid
    return high

firstCan = binSearch(A)
print(len(A)-firstCan)


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

M,N,K,T = inpl()
AA = inpl()

DD_di = []
LR = []
for i in range(K):
    L,R,D = inpl()
    LR.append((L,R))
    DD_di.append((D,i))

DD_di.sort()
DD_d = [D for D,i in DD_di]

def solve(x):
    idx = bisect.bisect_right(DD_d, x)
    path = [0]*(N+2)
    for D,i in DD_di[idx:]:
        L,R = LR[i]
        path[L] += 1
        path[R+1] -= 1

    t = N+1
    bp = path[0]
    for i in range(1,N+2):
        p = bp + path[i]
        if p > 0:
            t += 2
        bp = p

    return t <= T


OK = (10**5) * 2 + 10
NG = -1

while OK-NG > 1:
    mid = (OK+NG)//2
    if solve(mid):
        OK = mid
    else:
        NG = mid

ans = 0
for A in AA:
    if A >= OK:
        ans += 1

print(ans)


import sys
input = sys.stdin.readline

m,n,k,t=list(map(int,input().split()))
A=list(map(int,input().split()))
T=[tuple(map(int,input().split())) for i in range(k)]

NG=0
OK=2*10**5+1

while OK-NG>1:
    mid=(OK+NG)//2

    USE=[0]*(2*10**5+3)

    for l,r,d in T:
        if d>=mid:
            USE[l-1]+=1
            USE[r]-=1

    for i in range(1,2*10**5+3):
        USE[i]+=USE[i-1]

    #print(mid,USE[:10],(2*10**5+3-USE.count(0))*2+n+1)

    if (2*10**5+3-USE.count(0))*2+n+1<=t:
        OK=mid
    else:
        NG=mid

ANS=0
for a in A:
    if a>=OK-1:
        ANS+=1
print(ANS)

    

    


import sys
input = sys.stdin.readline

m,n,k,t=list(map(int,input().split()))
A=list(map(int,input().split()))
T=[tuple(map(int,input().split())) for i in range(k)]

A.sort(reverse=True)

SLIST=[0]*(2*10**5+2)

ind=0
for i in range(A[0],-1,-1):
    SLIST[i]=SLIST[i+1]
    
    while ind<m and A[ind]==i:
        SLIST[i]+=1
        ind+=1

SLIST=[SLIST[0]]+SLIST

NG=0
OK=2*10**5+1

while OK-NG>1:
    mid=(OK+NG)//2

    USE=[0]*(2*10**5+3)

    for l,r,d in T:
        if d>=mid:
            USE[l-1]+=1
            USE[r]-=1

    for i in range(1,2*10**5+3):
        USE[i]+=USE[i-1]

    #print(mid,USE[:10],(2*10**5+3-USE.count(0))*2+n+1)

    if (2*10**5+3-USE.count(0))*2+n+1<=t:
        OK=mid
    else:
        NG=mid

print(SLIST[OK])

    

    


import sys
input = sys.stdin.readline

m,n,k,t=list(map(int,input().split()))
A=list(map(int,input().split()))
T=[tuple(map(int,input().split())) for i in range(k)]


seg_el=1<<((n+2).bit_length())
seg_height=1+(n+2).bit_length()
SEG=[0]*(2*seg_el) 
LAZY=[0]*(2*seg_el)

def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=0:
            update_lazy = 1<<(seg_height - 1 - (ind.bit_length()))
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=1
            SEG[ind<<1]=SEG[1+(ind<<1)]=update_lazy
            LAZY[ind]=0

    while L!=R:
        if L > R:
            SEG[L]=1<<(seg_height - (L.bit_length()))
            LAZY[L]=1
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=1<<(seg_height - (R.bit_length()))
            LAZY[R]=1
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=SEG[ind<<1]+SEG[1+(ind<<1)]

def getvalues(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=0:
            update_lazy = 1<<(seg_height - 1 - (ind.bit_length()))
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=1
            SEG[ind<<1]=SEG[1+(ind<<1)]=update_lazy
            LAZY[ind]=0
            
    ANS=0

    while L!=R:
        if L > R:
            ANS+=SEG[L]
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS+=SEG[R]
            R//=(R & (-R))

    return ANS

T.sort(key=lambda x:x[2],reverse=True)

OK=2*10**5+1
ind=0

for i in range(2*10**5+2,-1,-1):

    while ind<k and T[ind][2]>=i:
        updates(T[ind][0], T[ind][1]+1, 1)
        ind+=1

    if getvalues(0, n+2)*2+n+1<=t:
        OK=i
    else:
        break

ANS=0
for a in A:
    if a>=OK-1:
        ANS+=1
print(ANS)


import sys
input = sys.stdin.readline

m,n,k,t=list(map(int,input().split()))
A=list(map(int,input().split()))
T=[tuple(map(int,input().split())) for i in range(k)]


seg_el=1<<((n+2).bit_length())
seg_height=1+(n+2).bit_length()
SEG=[0]*(2*seg_el) 
LAZY=[0]*(2*seg_el)

def indexes(L,R): # 遅延伝搬すべきノードのリストを返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=None:
            update_lazy = LAZY[ind] *(1<<(seg_height - 1 - (ind.bit_length())))
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=LAZY[ind]
            SEG[ind<<1]=SEG[1+(ind<<1)]=update_lazy
            LAZY[ind]=None

    while L!=R:
        if L > R:
            SEG[L]=x * (1<<(seg_height - (L.bit_length())))
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x * (1<<(seg_height - (R.bit_length())))
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=SEG[ind<<1]+SEG[1+(ind<<1)]

def getvalues(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=None:
            update_lazy = LAZY[ind] *(1<<(seg_height - 1 - (ind.bit_length())))
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=LAZY[ind]
            SEG[ind<<1]=SEG[1+(ind<<1)]=update_lazy
            LAZY[ind]=None
            
    ANS=0

    while L!=R:
        if L > R:
            ANS+=SEG[L]
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS+=SEG[R]
            R//=(R & (-R))

    return ANS

T.sort(key=lambda x:x[2],reverse=True)

OK=2*10**5+1
ind=0

for i in range(2*10**5+2,-1,-1):

    while ind<k and T[ind][2]>=i:
        updates(T[ind][0], T[ind][1]+1, 1)
        ind+=1

    if getvalues(0, n+2)*2+n+1<=t:
        OK=i
    else:
        break

ANS=0
for a in A:
    if a>=OK-1:
        ANS+=1
        
print(ANS)


import sys


def army(weak, traps, t_max, n):
    t = n + 1
    alone = [0] * (n + 1)
    for l, r, d in traps:
        if d <= weak:
            break
        alone[l - 1] += 1
        alone[r] -= 1
        
    interval = 0
    for loc in range(n + 1):
        interval += alone[loc]
        if interval:
            t += 2
            
#     print(t, t_max)
    return t <= t_max

# inf = open('input.txt', 'r')
# reader = (map(int, line.split()) for line in inf)
reader = (list(map(int, s.split())) for s in sys.stdin)

m, n, k, t_max = next(reader)
a = list(next(reader))
traps = []
for _ in range(k):
    l, r, d = next(reader)
    traps.append((l, r, d))

a.sort(reverse=True)
traps.sort(key=lambda x: x[2], reverse=True)
# print(a)
# print(traps)

# binary search of max amount of soldiers to pass
L = 0
R = m + 1
while L + 1 < R:
    check = (L + R) // 2
#     print(check, a[check - 1])
    if army(a[check - 1], traps, t_max, n):
        L = check
    else:
        R = check
#     print(L, R)
#     print()
    
print(L)
    
# inf.close()


# -*- coding: utf-8 -*-

import sys
from bisect import bisect_left
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok

M, N, K, T = MAP()
A = LIST()

LRD = []
for i in range(K):
    l, r, d = MAP()
    LRD.append((l, r, d))

def check(m):
    imos = [0] * (N+2)
    for l, r, d in LRD:
        if d > m:
            imos[l] += 1
            imos[r+1] -= 1
    imos = list(accumulate(imos))
    cnt = 0
    for i in imos:
        if i > 0:
            cnt += 1
    return cnt*2 + N+1 <= T

amx = max(A)
res = bisearch_min(0, amx+1, check)
A.sort()
idx = bisect_left(A, res)
cnt = M - idx
print(cnt)


(m, n, k, t) = list(map(int, input().split()))
a = list(map(int, input().split()))
trap = list()

for i in range(k):
    (x1, x2, x3) = list(map(int, input().split()))
    trap.append([x1, x2, x3])

trap.sort()
a.sort()

#print(trap)
#print(a)

x = -1
l = 0
r = len(a) - 1
s = 0
while r - l >= 0:
    x = (l + r) // 2
    weig = a[x]
    ltrap = 0
    rtrap = 0
    time = 0

    for i in trap:
        if i[2] > weig:
            if i[0] <= rtrap:
                rtrap = max(rtrap, i[1])
                time += i[0]-ltrap
                ltrap = i[0]

            else:
                time += rtrap - ltrap + 1
                rtrap = i[1]
                ltrap = i[0]
    time += rtrap - ltrap
    #print(x, weig, time)
    if 2*time + n + 1 <= t:
        s = max(s, len(a) - x)
        r = x - 1
    else:
        l = x + 1

print(s)

(m, n, k, t) = list(map(int, input().split()))
a = list(map(int, input().split()))
trap = list()
for i in range(k):
    (x1, x2, x3) = list(map(int, input().split()))
    trap.append([x1, x2, x3])
trap.sort()
a.sort()
x = -1
l = 0
r = len(a) - 1
s = 0
while r - l >= 0:
    x = (l + r) // 2
    weig = a[x]
    ltrap = 0
    rtrap = 0
    time = 0
    for i in trap:
        if i[2] > weig:
            if i[0] <= rtrap:
                rtrap = max(rtrap, i[1])
                time += i[0]-ltrap
                ltrap = i[0]
            else:
                time += rtrap - ltrap + 1
                rtrap = i[1]
                ltrap = i[0]
    time += rtrap - ltrap
    if 2*time + n + 1 <= t:
        s = max(s, len(a) - x)
        r = x - 1
    else:
        l = x + 1
print(s)


import sys
input = sys.stdin.readline

M, N, K, T = map(int, input().split())
A = list(map(int, input().split()))
LRD = [list(map(int, input().split())) for _ in range(K)]

A.append(10**15)
A.sort(reverse=True)

l = 0
r = M+1
while r-l > 1:
    m = (r+l)//2
    D_limit = A[m]
    
    P = [0]*(N+2)
    for L, R, D in LRD:
        if D_limit < D:
            P[L] += 1
            P[R+1] -= 1
    c = 0
    for i in range(N+1):
        P[i+1] += P[i]
        if P[i+1] > 0:
            c += 1
    #print(P, m)
    time = N+1 + 2*c
    #print(time)
    
    if time <= T:
        l = m
    else:
        r = m

print(l)

from sys import stdin

input = stdin.readline
#
# m, n, k, t = map(int, input().split())
#
# a = list(map(int, input().split()))
#
# t -= n
# mxr = [0] * (n+2)
# mxl = [0] * (n+2)
#
# trapr = [0] * (n+2)
# trapl = [0] * (n+2)
# for i in range(k):
#     l, r, d = map(int, input().split())
#     trapr[r] = max(trapr[r], d)
#     trapl[l] = max(trapl[l], d)
#
# for i in range(n+1)[::-1]:
#     mxr[i] = max(mxr[i + 1], trapr[i])
#
# for i in range(1, n+1):
#     mxl[i] = max(mxl[i - 1], trapl[i])
#
# ans = 0
# a.sort()
# from bisect import *
#
# for i in range(n+1):
#     f = i + t // 2
#     f = min(f, n)
#     mx = max(mxl[i], mxr[f + 1])
#     # print(n, m-bisect_left(a, mx))
#     ans = max(ans, m - bisect_left(a, mx))
#     # print(i, f, mx, ans)
#
# print(ans)
#
# trap = []
#
#
# def check(x):
#     avg = a[-x]
#     cost = n+1
#     nr = 0
#     for i in range(k):
#         xx, y, d = trap[i]
#         # print(avg,xx, y, d, cost,nr)
#         if d <= avg:
#             continue
#         if y > nr:
#             # print('1')
#             cost += (y - max(xx - 1, nr)) * 2
#             # print(xx,y,d,cost)
#             nr = y
#      # print(x, cost)
#     return cost <= t
#
#
# for i in range(k):
#     trap.append(list(map(int, input().split())))
#
# trap.sort()
#
# l = 0
# r = m+1
#
# while r - l > 1:
#     mid = (l + r) // 2
#     # print(mid)
#     if check(mid):
#         l = mid
#     else:
#         r = mid
#
#
# print(l)


def works(mid):
    ag = A[-mid]
    MAX = 0
    cur = 0
    out = N+1
    for l,r,d in traps:
        if d <= ag: continue
        if l > MAX:
            out += (MAX-cur)*2
            MAX,cur = r,l-1
        else:
            MAX = max(MAX,r)
    return out <= time
S,N,T,time = map(int,input().split())
A = list(map(int,input().split()))
traps = [tuple(map(int,input().split())) for _ in range(T)]
traps.sort()
traps.append((N+2,N+5,10**6))
A.sort()
lo = 0 #works
hi = S+1 #does not work
while hi - lo > 1:
    mid = (hi + lo) // 2
    if works(mid):
        lo = mid
    else:
        hi = mid

print(lo)

from sys import stdin

input = stdin.readline
#
# m, n, k, t = map(int, input().split())
#
# a = list(map(int, input().split()))
#
# t -= n
# mxr = [0] * (n+2)
# mxl = [0] * (n+2)
#
# trapr = [0] * (n+2)
# trapl = [0] * (n+2)
# for i in range(k):
#     l, r, d = map(int, input().split())
#     trapr[r] = max(trapr[r], d)
#     trapl[l] = max(trapl[l], d)
#
# for i in range(n+1)[::-1]:
#     mxr[i] = max(mxr[i + 1], trapr[i])
#
# for i in range(1, n+1):
#     mxl[i] = max(mxl[i - 1], trapl[i])
#
# ans = 0
# a.sort()
# from bisect import *
#
# for i in range(n+1):
#     f = i + t // 2
#     f = min(f, n)
#     mx = max(mxl[i], mxr[f + 1])
#     # print(n, m-bisect_left(a, mx))
#     ans = max(ans, m - bisect_left(a, mx))
#     # print(i, f, mx, ans)
#
# print(ans)
#
# trap = []
#
#
# def check(x):
#     avg = a[-x]
#     cost = n+1
#     nr = 0
#     for i in range(k):
#         xx, y, d = trap[i]
#         # print(avg,xx, y, d, cost,nr)
#         if d <= avg:
#             continue
#         if y > nr:
#             # print('1')
#             cost += (y - max(xx - 1, nr)) * 2
#             # print(xx,y,d,cost)
#             nr = y
#      # print(x, cost)
#     return cost <= t
#
#
# for i in range(k):
#     trap.append(list(map(int, input().split())))
#
# trap.sort()
#
# l = 0
# r = m+1
#
# while r - l > 1:
#     mid = (l + r) // 2
#     # print(mid)
#     if check(mid):
#         l = mid
#     else:
#         r = mid
#
#
# print(l)


def works(mid):
    ag = A[-mid]
    MAX = 0
    cur = 0
    out = N+1
    for l,r,d in traps:
        if d <= ag:
            continue
        if r > MAX:
            out += (r - max(l-1, MAX))*2
            MAX = r
        # if l > MAX:
        #     out += (MAX-cur)*2
        #     MAX,cur = r,l-1
        # else:
        #     MAX = max(MAX,r)
    return out <= time
S,N,T,time = map(int,input().split())
A = list(map(int,input().split()))
traps = [tuple(map(int,input().split())) for _ in range(T)]
traps.sort()
# traps.append((N+2,N+5,10**6))
A.sort()


lo = 0 #works
hi = S+1 #does not work
while hi - lo > 1:
    mid = (hi + lo) // 2
    if works(mid):
        lo = mid
    else:
        hi = mid

print(lo)

from sys import stdin

input = stdin.readline

m, n, k, t = list(map(int, input().split()))

a = list(map(int, input().split()))
#
# t -= n
# mxr = [0] * (n+2)
# mxl = [0] * (n+2)
#
# trapr = [0] * (n+2)
# trapl = [0] * (n+2)
# for i in range(k):
#     l, r, d = map(int, input().split())
#     trapr[r] = max(trapr[r], d)
#     trapl[l] = max(trapl[l], d)
#
# for i in range(n+1)[::-1]:
#     mxr[i] = max(mxr[i + 1], trapr[i])
#
# for i in range(1, n+1):
#     mxl[i] = max(mxl[i - 1], trapl[i])
#
# ans = 0
# a.sort()
# from bisect import *
#
# for i in range(n+1):
#     f = i + t // 2
#     f = min(f, n)
#     mx = max(mxl[i], mxr[f + 1])
#     # print(n, m-bisect_left(a, mx))
#     ans = max(ans, m - bisect_left(a, mx))
#     # print(i, f, mx, ans)
#
# print(ans)

trap = []


def check(x):
    avg = a[-x]
    cost = n+1
    nr = 0
    for i in range(k):
        xx, y, d = trap[i]
        # print(avg,xx, y, d, cost,nr)
        if d <= avg:
            continue
        if y > nr:
            # print('1')
            cost += (y - max(xx - 1, nr)) * 2
            # print(xx,y,d,cost)
            nr = y
     # print(x, cost)
    return cost <= t


for i in range(k):
    trap.append(list(map(int, input().split())))

trap.sort()
a.sort()

l = 0
r = m+1

while r - l > 1:
    mid = (l + r) // 2
    # print(mid)
    if check(mid):
        l = mid
    else:
        r = mid


print(l)

#
#
# def works(mid):
#     ag = A[-mid]
#     MAX = 0
#     cur = 0
#     out = N+1
#     for l,r,d in traps:
#         if d <= ag:
#             continue
#         if r > MAX:
#             out += (r - max(l-1, MAX))*2
#             MAX = r
#         # if l > MAX:
#         #     out += (MAX-cur)*2
#         #     MAX,cur = r,l-1
#         # else:
#         #     MAX = max(MAX,r)
#     return out <= time
# S,N,T,time = map(int,input().split())
# A = list(map(int,input().split()))
# traps = [tuple(map(int,input().split())) for _ in range(T)]
# traps.sort()
# # traps.append((N+2,N+5,10**6))
# A.sort()
#
#
# lo = 0 #works
# hi = S+1 #does not work
# while hi - lo > 1:
#     mid = (hi + lo) // 2
#     if works(mid):
#         lo = mid
#     else:
#         hi = mid
#
# print(lo)


m, n, k, t = list(map(int, input().split()))

soldiers = list(map(int, input().split()))
traps = []
for _ in range(k):
    l, r, d = list(map(int, input().split()))
    traps.append((l, r, d))

soldiers.sort(reverse=True)    
traps.sort()

def cost(count):
    agil = soldiers[count-1] if count>0 else 10**6
    current_begin = 0
    current_end = -1
    inter_cost = 0
    
    for l, r, d in traps:
        if d <= agil:
            continue
        if l > current_end:
            inter_cost += 2 * (current_end - current_begin + 1)
            current_begin = l
        current_end = max(current_end, r)
        
    inter_cost += 2 * (current_end - current_begin + 1)
    
    return inter_cost + n+1
    
def bin_search(lo, hi):
    if lo+1 >= hi:
        return lo
        
    mid = (lo+hi)//2
    
        
    if cost(mid) <= t:
        lo = mid
    else:
        hi = mid
        
    return bin_search(lo, hi)
    
    
result = bin_search(0, m+1)

print(result)



from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

(m,n,k,T)= list(map(int, input().split()))
a = list(map(int,input().split()))
DD = []
LR = []

for i in range(k):
    L,R,D = map(int,input().split())
    LR.append((L,R))
    DD.append((D,i))
DD.sort()
DD_id = [D for D,i in DD]

def Solve(x):
    idx = bisect.bisect_right(DD_id, x)
    path=[0] * (n+2)
    for X,i in DD[idx:]:
        LL,RR = LR[i]
        path[LL] +=1
        path[RR+1] -=1
    t = n+1
    bp = path[0]
    for i in range(1,n+2):
        p = bp + path[i]
        if p>0:
            t+=2
        bp = p
    
    return t<=T 


L = -1
R = 2*10**5+2
while R-L>1:
    mid =(L+R)//2
    if Solve(mid):
        R = mid
    else:
        L = mid

ans = 0
for i in a:
    if i >= R:
        ans += 1
print(ans)

class Traps():
    def __init__(self,l,r,d):
        self.before_l = l - 1
        self.r = r
        self.d = d

def qujianbingji(x,y):
    if y[0]<x[0]:
        if y[1]<x[0]:
            return [y,x]
        elif y[1]<=x[1]:
            z = [y[0],x[1]]
            return [z]
        else:
            return [y]
    elif y[0]<x[1]:
        if y[1]<=x[1]:
            return [x]
        else:
            z = [x[0],y[1]]
            return [z]
    else:
        return [x,y]


def main():
    m, n, k, t = map(int, input().split())
    lista = list(map(int, input().split()))
    lista.sort(reverse=True)
    list_traps = []
    for i in range(k):
        l, r, d = map(int, input().split())
        list_traps.append(Traps(l,r,d))
    list_traps.sort(key=lambda x:x.before_l)
    T = 0
    left, right = -1, m
    while right-left>1:#？？？？？？？
        dangerous_traps = []
        mid = (left+right)//2

        for trap in list_traps:
            if trap.d > lista[mid]:
                dangerous_traps.append(trap)

        if dangerous_traps == []:
            T = n + 1
        else:
            space = 0
            finalbing = [[dangerous_traps[0].before_l, dangerous_traps[0].r]]
            for dangerous_trap in dangerous_traps:
                c = qujianbingji(finalbing[-1], [dangerous_trap.before_l, dangerous_trap.r])
                del finalbing[-1]
                if len(c) == 2:
                    finalbing.append(c[0])
                    finalbing.append(c[1])
                else:
                    finalbing.append(c[0])
            lenfb = len(finalbing)
            if lenfb == 1:
                T = n + 1 + (finalbing[0][1] - finalbing[0][0]) * 2
            else:
                for x in range(lenfb - 1):
                    space += finalbing[x + 1][0] - finalbing[x][1]
                maxlen = finalbing[-1][1] - finalbing[0][0]
                T = n + 1 + 2 * (maxlen - space)

        if T > t:
            left, right = left, mid
            count = mid

        else:
            left, right = mid, right
            count = mid + 1
    print(count)

    # for i in range(0,m):
    #
    #     dangerous_traps = []
    #     list_r = []
    #     list_l = []
    #     for trap in list_traps:
    #         if trap.d > lista[i]:
    #             dangerous_traps.append(trap)
    #             list_r.append(trap.r)
    #             list_l.append(trap.before_l)
    #     if dangerous_traps == []:
    #         T = n+1
    #     else:
    #         space = 0
    #         lenth = len(dangerous_traps)
    #         finalbing = [[dangerous_traps[0].before_l,dangerous_traps[0].r]]
    #         for dangerous_trap in dangerous_traps:
    #             c = qujianbingji(finalbing[-1],[dangerous_trap.before_l,dangerous_trap.r])
    #             del finalbing[-1]
    #             if len(c)==2:
    #                 finalbing.append(c[0])
    #                 finalbing.append(c[1])
    #             else:
    #                 finalbing.append(c[0])
    #         lenfb =len(finalbing)
    #         if lenfb == 1:
    #             T = n+1 + (finalbing[0][1]-finalbing[0][0])*2
    #         else:
    #             for x in range(lenfb-1):
    #                 space += finalbing[x+1][0]-finalbing[x][1]
    #             maxlen = finalbing[-1][1]-finalbing[0][0]
    #             T = n + 1 + 2 * (maxlen - space)
    #
    #     if T > t:
    #         left, right = mid,right
    #         count = i
    #     else:
    #         left,right = left, mid
    #         count = i+1
    # print(count)

main()