#2027 · Lá chắn nhiều tầng

Trên một tuyến đường không gian có N trạm quan sát, trạm thứ i nằm tại tọa độ x_i và cần ít nhất h_i lớp lá chắn hoạt động đồng thời.

Có M máy phát lá chắn. Máy phát thứ j có thể bảo vệ mọi trạm có tọa độ nằm trong đoạn [l_j, r_j].

Mỗi máy phát được bật hoặc không bật. Nếu bật, nó đóng góp đúng 1 lớp lá chắn cho mọi trạm nằm trong đoạn phủ của nó.

Hãy tìm số máy phát ít nhất cần bật để mọi trạm đều có đủ số lớp lá chắn yêu cầu. Nếu không thể, in -1.

N \space M

x_1 \space h_1

x_2 \space h_2

...

x_N \space h_N

l_1 \space r_1

l_2 \space r_2

...

l_M r_M

In ra một số nguyên duy nhất: số máy phát ít nhất cần bật. Nếu không thể thỏa mãn yêu cầu, in: -1

• 1 \leq N \leq 6 \times 10^4
• 1 \leq M \leq8 \times 10^4
• 0 \leq x_i \leq 10^8
• 0 \leq l_i, r_i \leq 10^8
• 1 \leq h_i \leq 120