Василий любит после завершения рабочего дня поиграть в свою любимую компьютерную игру.
Игра происходит в двумерном мире, начиная с момента времени $$$0$$$. Василий может выбрать любую клетку мира и появиться в ней. Далее каждую единицу времени Василий может остаться на своем прежнем месте или переместиться из текущей клетки (x, y) в одну из следующих: (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1).
Чтобы ускорить передвижение по миру в игре существует $$$n$$$ вышек для перемещения, $$$i$$$-я вышка расположена в клетке ($$$xa_i, ya_i$$$). Чтобы иметь возможность мгновенно переместиться к вышке из любой точки мира, необходимо ее активировать. Активация вышки $$$i$$$ происходит в момент, когда игрок находится в клетке ($$$xa_i, ya_i$$$), после этого вышка остается активной на протяжении всей игры.
Также Василию известно, что в игре есть $$$m$$$ квестов, $$$i$$$-й из которых можно выполнить мгновенно, находясь в момент времени $$$t_i$$$ в клетке ($$$xb_i, yb_i$$$).
Василий хочет узнать, какое максимальное количество квестов он сможет выполнить, если будет оптимально перемещаться по игровому миру.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$0 \le n \le 14, 1 \le m \le 100$$$) — количество вышек и квестов.
Следующие $$$n$$$ строк содержат по два целых числа $$$xa_i, ya_i$$$ ($$$1 \le xa_i, ya_i \le 10^6$$$) — координаты вышек.
Следующие $$$m$$$ строк содержат по три целых числа $$$xb_i$$$, $$$yb_i$$$ и $$$t_i$$$ ($$$1 \le xb_i, yb_i \le 10^6$$$, $$$1 \le t_i \le 10^9$$$) — координаты квеста и время, в которое его можно выполнить.
Гарантируется, что все координаты во входных данных различны.
Выведите одно целое число — максимальное количество квестов, которое сможет выполнить Василий.
3 4 1 1 2 3 5 2 2 2 12 5 1 4 6 2 11 3 5 10
3
В первом тестовом примере одной из возможных последовательностей действий Василия может быть следующая:
- Начать в клетке $$$(3, 2)$$$
- В момент времени $$$1$$$ перемещается в клетку $$$(4, 2)$$$
- В момент времени $$$2$$$ перемещается в клетку $$$(5, 2)$$$. Посетив эту клетку, Василий активирует вышку номер $$$3$$$.
- В момент времени $$$3$$$ перемещается в клетку $$$(5, 1)$$$, где ему остается подождать еще $$$1$$$ момент времени, чтобы выполнить $$$2$$$ квест
- В момент времени $$$5$$$ перемещается в клетку $$$(5, 2)$$$
- В момент времени $$$6$$$ перемещается в клетку $$$(5, 3)$$$
- В момент времени $$$7$$$ перемещается в клетку $$$(5, 4)$$$
- В момент времени $$$8$$$ перемещается в клетку $$$(5, 5)$$$
- В момент времени $$$9$$$ перемещается в клетку $$$(4, 5)$$$
- В момент времени $$$10$$$ перемещается в клетку $$$(3, 5)$$$. Переместившись в эту клетку Василий выполнит $$$4$$$ квест
- В момент времени $$$10$$$ мгновенно переместиться в ранее активированную вышку в клетке $$$(5, 2)$$$
- В момент времени $$$11$$$ перемещается в клетку $$$(6, 2)$$$. Переместившись в эту клетку Василий выполнит $$$3$$$ квест
- Квест под номером $$$1$$$ Василий не успеет выполнить, потому что вышка в клетке $$$(2, 3)$$$ не была активирована
