Trò chơi với bẫy

Bạn có $m$ chiến binh, chiến binh thứ $i$ có chỉ số nhanh nhẹn $a_i$. Màn chơi là một đoạn thẳng từ điểm $0$ (vị trí xuất phát của bạn và đội) đến điểm $n+1$ (vị trí trùm cuối).

Trên đoạn từ $1$ đến $n$ có $k$ cái bẫy. Bẫy thứ $i$ được mô tả bởi ba số $l_i$, $r_i$, $d_i$: bẫy đặt tại điểm $l_i$ với độ nguy hiểm $d_i$; bất cứ chiến binh nào có chỉ số nhanh nhẹn nhỏ hơn $d_i$ bước vào điểm $l_i$ sẽ bị tiêu diệt ngay lập tức. Khi bạn (một mình) di chuyển đến điểm $r_i$ thì bẫy $i$ bị vô hiệu hoá và không còn nguy hiểm. Các bẫy không ảnh hưởng đến bản thân bạn, chỉ ảnh hưởng đến đội.

Bạn có tối đa $t$ giây để đưa đội đến chỗ trùm cuối. Trước khi bắt đầu, bạn chọn ra một tập con các chiến binh sẽ đi cùng; sau đó bạn phải đưa toàn bộ các chiến binh đã chọn từ điểm $0$ đến điểm $n+1$. Trong mỗi giây bạn có thể thực hiện một trong các thao tác:

• Nếu bạn đang ở vị trí $x$, di chuyển đến $x+1$ hoặc $x-1$ (một mình, không có đội). Tốn $1$ giây.
• Nếu bạn ở vị trí $x$ và đội cũng đang ở $x$, di chuyển cả đội đến $x+1$ hoặc $x-1$. Không được thực hiện nếu điểm đến chứa một bẫy chưa vô hiệu hoá với $d_i$ lớn hơn chỉ số nhanh nhẹn của một chiến binh nào đó trong đội. Tốn $1$ giây.
• Nếu bạn ở vị trí $x$ và có bẫy $i$ với $r_i=x$, bạn có thể vô hiệu hoá bẫy đó tức thì (không tốn giây).

Sau mỗi thao tác, cả toạ độ của bạn lẫn toạ độ của đội đều phải là số nguyên.

Hãy tìm số lượng chiến binh lớn nhất mà bạn có thể chọn sao cho đưa được toàn bộ họ đến vị trí $n+1$ trong không quá $t$ giây.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên $m$, $n$, $k$, $t$ ($1\le m,n,k,t\le 2·{10}^5$, $n<t$).
• Dòng thứ hai chứa $m$ số nguyên $a_1,a_2,\dots ,a_m$ ($1\le a_i\le 2·{10}^5$) — chỉ số nhanh nhẹn của các chiến binh.
• $k$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $l_i$, $r_i$, $d_i$ ($1\le l_i\le r_i\le n$, $1\le d_i\le 2·{10}^5$) — mô tả bẫy thứ $i$.

Dữ liệu ra

Một số nguyên duy nhất — số chiến binh tối đa có thể đưa đến trùm cuối trong không quá $t$ giây.

Ràng buộc

• $1\le m,n,k,t\le 2·{10}^5$
• $n<t$
• $1\le a_i,d_i\le 2·{10}^5$
• $1\le l_i\le r_i\le n$

Ví dụ