Favorite Game

题意翻译

考虑一个在二维平面上的游戏，玩家选择一个整点并在 $0$ 时刻到达，接下来每秒玩家可以不动或向上或下或左或右走一步。有 $n$ 个传送门第 $i$ 个在 $(xa_i,ya_i)$，初始时传送门都未被激活，当玩家到达一个未激活传送门时此传送门被激活，之后玩家在任意时刻任意位置都可以立刻瞬移到这个传送门。有 $m$ 个任务第 $i$ 个任务要求玩家在 $t_i$ 时刻时恰好在 $(xb_i,yb_i)$ 位置。求玩家最多可以完成几个任务。 - $n\le 14,m\le 100$。

题目描述

After William is done with work for the day, he enjoys playing his favorite video game. The game happens in a 2D world, starting at turn $ 0 $ . William can pick any cell in the game world and spawn in it. Then, each turn, William may remain at his current location or move from the current location (x, y) to one of the following locations: (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1). To accelerate movement the game has $ n $ fast travel towers. $ i $ -th tower is located at location ( $ xa_i, ya_i $ ). To be able to instantly travel to the tower from any location in the game world it must first be activated. Activation of tower $ i $ happens at the moment when the player is in cell ( $ xa_i, ya_i $ ) after this the tower remains active throughout the entire game. William also knows that the game has $ m $ quests. $ i $ -th quest can be completed instantly by being at location ( $ xb_i, yb_i $ ) on turn $ t_i $ . William wants to find out the maximal number of quests he will be able to complete by optimally traversing the game world.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 0 \le n \le 14, 1 \le m \le 100 $ ), which are the number of towers and the number of quests, respectively. Each of the next $ n $ lines contains two integers $ xa_i, ya_i $ ( $ 1 \le xa_i, ya_i \le 10^6 $ ), which are the coordinates of fast travel towers. Each of the next $ m $ lines contains two integers $ xb_i $ , $ yb_i $ and $ t_i $ ( $ 1 \le xb_i, yb_i \le 10^6 $ , $ 1 \le t_i \le 10^9 $ ), which are the coordinates of quests and the turn at which it may be completed. It is guaranteed that all locations in a test are different.

输出格式

Print a single number — the maximal number of quests William will be able to complete.

输入输出样例

输入样例 #1

3 4
1 1
2 3
5 2
2 2 12
5 1 4
6 2 11
3 5 10

输出样例 #1

3

说明

In the first sample test one of the possible sequences of William's actions is as follows: - Spawn at $ (3, 2) $ - On turn $ 1 $ move to $ (4, 2) $ - On turn $ 2 $ move to $ (5, 2) $ . By visiting this cell William activates tower number $ 3 $ . - On turn $ 3 $ move to $ (5, 1) $ , where he waits for $ 1 $ turn to complete the $ 2 $ nd quest - On turn $ 5 $ move to $ (5, 2) $ - On turn $ 6 $ move to $ (5, 3) $ - On turn $ 7 $ move to $ (5, 4) $ - On turn $ 8 $ move to $ (5, 5) $ - On turn $ 9 $ move to $ (4, 5) $ - On turn $ 10 $ move to $ (3, 5) $ . By moving to this location William will complete the $ 4 $ th quest - On turn $ 10 $ instantly move to an already activated fast travel tower at $ (5, 2) $ - On turn $ 11 $ move to $ (6, 2) $ . By moving to this location William will complete the $ 3 $ rd quest - William will not be able to complete the quest number $ 1 $ , because the tower at $ (2, 3) $ was not activated