Xe về nhà

Trên một bàn cờ kích thước ${10}^9\times {10}^9$, các hàng được đánh số từ dưới lên trên từ $1$ đến ${10}^9$, các cột được đánh số từ trái sang phải từ $1$ đến ${10}^9$. Ô ở cột $x$, hàng $y$ có tọa độ $(x,y)$.

Một quân xe đang đứng ở ô $(1,1)$ và muốn về nhà: đi tới một ô bất kỳ thuộc hàng trên cùng (hàng số ${10}^9$). Quân xe mỗi bước di chuyển tới một ô bất kỳ cùng hàng hoặc cùng cột với ô hiện tại, với điều kiện trên đường đi không vướng vật cản nào.

Trên bàn cờ có hai loại vật cản:

• Vật cản dọc, xác định bởi một số $x$: một đường chắn vô hạn nằm giữa cột $x$ và cột $x+1$.
• Vật cản ngang, xác định bởi ba số $x_1,x_2,y$: một đoạn chắn nằm sát mép trên của các ô thuộc hàng $y$, từ cột $x_1$ đến cột $x_2$. Hai vật cản ngang bất kỳ không có điểm chung (nhưng vật cản ngang có thể chạm vật cản dọc).

Quân xe có thể xóa bỏ vật cản, nhưng việc này rất tốn sức. Hãy tìm số vật cản ít nhất cần xóa để quân xe có thể đi từ $(1,1)$ tới một ô nào đó ở hàng ${10}^9$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$: số vật cản dọc và số vật cản ngang.
• $n$ dòng tiếp theo, mỗi dòng chứa một số nguyên $x$: vật cản dọc nằm giữa cột $x$ và cột $x+1$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $x_1,x_2,y$: vật cản ngang nằm sát mép trên các ô hàng $y$, từ cột $x_1$ đến cột $x_2$.

Tất cả vật cản đôi một khác nhau, và hai vật cản ngang bất kỳ không có điểm chung.

Dữ liệu ra

In ra một số nguyên duy nhất: số vật cản ít nhất cần xóa.

Ràng buộc

• $0\le n,m\le {10}^5$
• $1\le x<{10}^9$
• $1\le x_1\le x_2\le {10}^9$, $1\le y<{10}^9$

Ví dụ