TopCoder

User's AC Ratio

86.7% (26/30)

Submission's AC Ratio

23.5% (32/136)

Description

在競賽圈有個潛規則,你如果想要變強,你就要去吃碗拉麵,而且你吃的拉麵越好吃,你就會變得越強。
在天龍國裡,共有 $N, (N \leq 2 \times10^ 3)$ 家麵店,每一家拉麵店都能夠用三個參數表示 $x_i, y_i, d_i (-10^ 9 \leq x_i, y_i \leq 10^ 9), (1 \leq d_i \leq N)$
其中 $x_i, y_i$ 代表麵店的座標,而 $d_i$ 代表他們的拉麵美味程度,而且對於兩兩不同的麵店,他們的美味程度不會重複。

有 $M, (M \leq 2 \times 10^ 3)$ 位競賽選手散落在各地,第 $i$ 位選手現在在座標 $X_i, Y_i, (-10^ 9 \leq X_i, Y_i \leq 10^ 9)$,想要去吃拉麵。
每個人都想吃最好吃的拉麵,
可是如果每個人都擠在同一間拉麵店的話,就要等很久。

聰明的你想到了一個辦法。
你規定所有人都只能前往和它距離 $K$ 以內的拉麵店。
其中兩個座標 $(x_1, y_1), (x_2, y_2)$ 的距離定為 $max(|x_1-x_2|, |y_1-y_2|)$

在這樣的狀況下,所有人都會前往他可以去的拉麵店中,做出最美味拉麵的店。

這樣一來,就不會所有人都擠在同一間拉麵店裡了

現在,你想知道,在精確的限制下,最多能有幾間拉麵店有人光顧

Input Format

第一行 $2$ 個正整數 $N, M$ 分別代表拉麵店的數量及選手的數量
接下來 $N$ 行,每行都有三個整數 $x_i, y_i, d_i$ 其中意義參考題敘
接下來 $M$ 行,每行有兩個整數 $X_i, Y_i$ 其中意義參考題敘

Output Format

請輸出一個整數代表答案

Sample Input

3 3
1 1 1
2 1 2
2 3 3
0 1
1 3
3 3

Sample Output

2

Hints

關於範測一
當我們將 $K$ 設定為 1 的時候
編號為 1 的人將去 A (評價為 1) 的餐廳

而編號為 2, 3 都會去 C ( 評價為 3) 的餐廳

所以總共有兩間餐廳有人光顧
而且沒有其他的 $K$ 可以讓更多餐廳有人光顧
hint

Problem Source

by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0~4 $N, M \leq 5$ 8
2 5~9 $N \leq 2$ 8
3 10~14 $(N, M \leq 50), (0 \leq x_i, y_i, X_i, Y_i \leq 100)$ 20
4 15~19 $0 \leq x_i, y_i, X_i, Y_i, \leq 1000$ 24
5 0~34 No additional limits 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 256000 65536 1 5
1 1000 256000 65536 1 5
2 1000 256000 65536 1 5
3 1000 256000 65536 1 5
4 1000 256000 65536 1 5
5 1000 256000 65536 2 5
6 1000 256000 65536 2 5
7 1000 256000 65536 2 5
8 1000 256000 65536 2 5
9 1000 256000 65536 2 5
10 1000 256000 65536 3 5
11 1000 256000 65536 3 5
12 1000 256000 65536 3 5
13 1000 256000 65536 3 5
14 1000 256000 65536 3 5
15 2000 256000 65536 4 5
16 2000 256000 65536 4 5
17 2000 256000 65536 4 5
18 2000 256000 65536 4 5
19 2000 256000 65536 4 5
20 2000 256000 65536 5
21 2000 256000 65536 5
22 2000 256000 65536 5
23 2000 256000 65536 5
24 2000 256000 65536 5
25 2000 256000 65536 5
26 2000 256000 65536 5
27 2000 256000 65536 5
28 2000 256000 65536 5
29 2000 256000 65536 5
30 2000 256000 65536 5
31 2000 256000 65536 5
32 2000 256000 65536 5
33 2000 256000 65536 5
34 2000 256000 65536 5