На шахматной доске шириной $$$10^9$$$ и высотой $$$10^9$$$ строки нумеруются снизу вверх от $$$1$$$ до $$$10^9$$$, а столбцы слева направо от $$$1$$$ до $$$10^9$$$. Поэтому каждой клетке шахматной доски можно присвоить координаты $$$(x,y)$$$, где $$$x$$$ — номер столбца, а $$$y$$$ — номер строки.
На этой доске каждый день проходят бои между чёрными и белыми фигурами. Сегодня победу одержали чёрные, но какой ценой? В живых осталась лишь ладья, и то, загнанная в левый нижний угол — клетку с координатами $$$(1,1)$$$. Но она все равно счастлива, ведь победа одержана и надо её отпраздновать! Для того чтобы это сделать, ладье нужно вернуться домой, а именно — на верхнюю сторону поля (то есть в любую клетку, которая находится в строке под номером $$$10^9$$$).
Все было бы хорошо, но коварные белые фигуры перед концом игры поставили заклинания в некоторых местах поля. Заклинания бывают двух видов:
- Вертикальные. Они задаются одним числом $$$x$$$. Такие заклинания создают бесконечную блокирующую прямую между столбцами $$$x$$$ и $$$x+1$$$.
- Горизонтальные. Они задаются тремя числами $$$x_1$$$, $$$x_2$$$, $$$y$$$. Такие заклинания создают блокирующий отрезок, который проходит через верхнюю сторону клеточек, которые находятся в строке $$$y$$$ и в столбцах с $$$x_1$$$ по $$$x_2$$$ включительно. Особенность этих заклинаний заключается в том, что невозможно такое, чтобы некая пара таких заклинаний имела общую точку. Обратите внимание, что горизонтальные заклинания могут иметь общие точки с вертикальными заклинаниями.
Напомним, что ладья — это шахматная фигура, которая может за один ход передвинуться на любую точку, которая находится в одной строке или столбце с её исходным положением. В нашей задаче ладья может за один ход передвинуться из клетки $$$(r_0,c_0)$$$ в клетку $$$(r_1,c_1)$$$ только при условии, что $$$r_1 = r_0$$$ или $$$c_1 = c_0$$$ и при этом на пути между этими клетками нет блокирующих прямых или блокирующих отрезков (Для лучшего понимая смотрите на примеры из условия).
К счастью, ладья может убирать заклинания, но для этого ей приходится использовать нечеловеческие усилия. Она хочет убрать минимально возможное количество заклинаний, чтобы после этого она могла вернуться домой. Найдите это количество!
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$0 \le n,m \le 10^5$$$) — количество вертикальных и горизонтальные заклинаний.
Каждая из следующих $$$n$$$ строк содержит одно целое число $$$x$$$ ($$$1 \le x < 10^9$$$) — описание вертикального заклинания. Оно описывает блокирующую прямую между столбцами $$$x$$$ и $$$x+1$$$.
Каждая из следующих $$$m$$$ строк содержит три целых числа $$$x_1$$$, $$$x_2$$$ и $$$y$$$ ($$$1 \le x_{1} \le x_{2} \le 10^9$$$, $$$1 \le y < 10^9$$$) — числа, описывающие горизонтальное заклинание. Они описывают блокирующий отрезок на верхних сторонах клеточек, которые находятся в строке под номером $$$y$$$, в столбцах с $$$x_1$$$ до $$$x_2$$$ включительно.
Гарантируется что все заклинания различны, а также то, что для каждой пары горизонтальных заклинаний верно, что отрезки, которые их задают, не имеют общих точек.
В единственной строке выведите одно число — минимальное количество заклинаний, которые понадобится снять ладье, чтобы добраться из клетки $$$(1,1)$$$ до хотя бы одной клетки в строке под номером $$$10^9$$$.
2 3
6
8
1 5 6
1 9 4
2 4 2
1
1 3
4
1 5 3
1 9 4
4 6 6
1
0 2
1 1000000000 4
1 1000000000 2
2
0 0
0
2 3
4
6
1 4 3
1 5 2
1 6 5
2
В первом примере, чтобы ладья могла вернуться домой, достаточно убрать второе горизонтальное заклинание.
Иллюстрация к первому примеру. Слева — как выглядело поле изначально. Справа — как оно выглядело после того, как было убрано второе горизонтальное заклинание. На изображении справа также показан путь, по которому двигалась бы ладья домой. Во втором примере для того, чтобы ладья могла вернуться домой, достаточно убрать единственное вертикальное заклинание. Если же мы попытаемся удалить лишь одно из горизонтальных заклинаний, то это не даст ладье возможность добраться домой, ведь ей сверху будет преграждать путь одно из оставшихся (первое или второе) горизонтальных заклинаний, а справа — вертикальное заклинание.
Иллюстрация ко второму примеру. Слева — как выглядело поле изначально. Справа — как оно выглядело после того, как было убрано вертикальное заклинание. На изображении справа также показан путь, по которому двигалась бы ладья домой. В третьем примере у нас есть два горизонтальных заклинания, которые проходят через всё поле. Эти заклинания обойти нельзя, значит, нам надо убрать оба заклинания.
Иллюстрация к третьему примеру. Слева — как выглядело поле изначально. Справа — как оно выглядело после того, как были убраны горизонтальные заклинания. На изображении справа также показан путь, по которому двигалась бы ладья домой. В четвёртом примере, у нас нет заклинаний, значит, ничего убирать не надо.
В пятом примере мы можем убрать первое вертикальное и третье горизонтальное заклинания.
Иллюстрация к пятому примеру. Слева — как выглядело поле изначально. Справа — как оно выглядело после того, как были убраны заклинания, указанные выше. Также показан путь, по которому двигалась бы ладья домой.
