Favorite Game
Contest: Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 3300
Tags: bitmasks, dp

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.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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

Example input:
3 4
1 1
2 3
5 2
2 2 12
5 1 4
6 2 11
3 5 10

Example output:
3

Editorial:
For convenience we will sort quests by time.
Let's make two DP:
$$$F(mask, done_q)$$$ — minimum amount of time it takes to visit the set of $$$mask$$$ towers and complete $$$done_q$$$ quests. William is in one of the towers.
$$$G(mask, q)$$$ — maximum number of quests that William can complete if he visited a set of $$$mask$$$ towers, and the last completed quest is quest number $$$q$$$. It is assumed that the current time for this state is equal to $$$t_q$$$ and William is at the coordinate $$$(xb_q, yb_q)$$$.
DP transitions will be as follows:
Transition describing a visit to the new tower $$$tower_{new}$$$, assumed that William was in the tower before:
$$$F(mask, done_q) + distance_{tower}(mask, tower_{new}) \underset{minimize}{\rightarrow} F(mask \cup tower_{new}, done_q)$$$, $$$tower_{new} \notin mask$$$,
where $$$distance_{tower}(mask, tower_{new})$$$ — minimum distance among all towers from the set $$$mask$$$ to the tower $$$tower_{new}$$$.
Transition describing a visit to a new quest, assumed that William was in the tower before:
$$$(done_q + 1) \underset{minimize}{\rightarrow} G(mask, q)$$$, only if $$$F(mask, done_q) + distance_{quest}(mask, q) \leq t_q$$$,
where $$$distance_{quest}(mask, q)$$$ — minimum distance among all towers from the set $$$mask$$$ to the quest $$$q$$$.
Transition describing visiting a new quest immediately after the old one, without visiting new towers:
$$$G(mask, q) + 1 \underset{minimize}{\rightarrow} G(mask, q_{new})$$$, only if $$$t_q + min(distance(q, q_{new}), distance_{quest}(mask, q_{new})) \leq t_{q_{new}}$$$,
where $$$distance(q, q_{new})$$$ — distance between two quests (without instant travel),
$$$min(distance(q, q_{new}), distance_{quest}(mask, q_{new}))$$$ — choosing the optimal route: either directly to the quest, or through the tower.
Transition describing a visit to a new tower, immediately after William visited quest number $$$q$$$:
$$$t_q + min(distance(q, tower_{new}), distance_{tower}(mask, tower_{new}) \underset{minimize}{\rightarrow} F(mask \cup tower_{new}, G(mask, q))$$$, $$$tower_{new} \notin mask$$$,
where $$$distance(q, tower_{new})$$$ — distance from quest number $$$q$$$ to tower number $$$tower_{new}$$$,
$$$distance_{tower}(mask, tower_{new})$$$ — minimum distance from one of the towers from the set $$$mask$$$ to the tower $$$tower_{new}$$$.
Initial states will be:
$$$G(0, q) = 1$$$, for each quest $$$q$$$ — William can choose any starting coordinate. Therefore, he can choose to start at the coordinate with the quest and wait for it.
All other states initialized as $$$G = -\infty$$$.
$$$F(\{tower\}, 0) = 0$$$, for each tower $$$tower$$$ — William can choose any starting coordinate. Therefore, he can choose the coordinate of the tower and be in it at time $$$0$$$.
All other states initialized as $$$F = \infty$$$.
Answer:
The answer is the maximum value among all $$$G(mask, q)$$$.
Time complexity:
There are $$$O(2^N \cdot M)$$$ states in total. From each state there are $$$O(N + M)$$$ transitions. Hence the time complexity is $$$O(2^N \cdot M \cdot (N + M))$$$.