Олимпиадный тренинг

Задача . F. Любимая игра

Задача

$\text{[math]}$

Василий любит после завершения рабочего дня поиграть в свою любимую компьютерную игру.

Игра происходит в двумерном мире, начиная с момента времени $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, 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)$ не была активирована

Примеры

№	Входные данные	Выходные данные
1	3 4 1 1 2 3 5 2 2 2 12 5 1 4 6 2 11 3 5 10	3

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет