A14359 | Favorite Game

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.