Организаторы олимпиады заранее приготовили N футболок, размер i-й футболки Si. На олимпиаде участвуют M человек, у каждого из них свои предпочтения по размеру: i-му человеку подходят футболки размерами от Li до Ri включительно. Участник остается довольным, если получает подходящую футболку. Какое максимальное количество участников могут быть довольны? Одну футболку можно дать только одному из участников.
Входные данные
В первой строке находятся два целых числа N и M(1≤N,M≤105).
Во второй строке находятся N целых числа S1,S2,…,Sn (1≤Si≤109) — размеры футболок.
В следующих M строках находятся по два целых числа Li и Ri(1≤Li≤Ri≤109) — подходящий диапазон размеров.
Выходные данные
Выведите максимальное количество участников, которые могут получить подходящую футболку.
Система оценки
В задаче 10 тестов. Каждый из них оценивается в 10 баллов.
Тесты 1-2. Примеры из условия.
Тесты 3-4: Li=Ri.
Тесты 5-7: Ri<Li + 1. Подходящие диапазоны размеров не пересекаются и идут в порядке возрастания.
Тесты 8-10: без дополнительных ограничений.
Примечание
Во втором примере только первая футболка подходит второму и третьему участнику. Но по условию только один из них может её получить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
3 5
1 10
4 6
|
2
|
|
2
|
3 5
1 3 8
1 10
4 7
1 2
4 6
9 10
|
2
|