{"problem":{"name":"Jumping Takahashi 2","description":{"content":"There are $N$ trampolines on a two-dimensional planar town where Takahashi lives. The $i$\\-th trampoline is located at the point $(x_i, y_i)$ and has a power of $P_i$. Takahashi's jumping ability is d","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc257_d"},"statements":[{"statement_type":"Markdown","content":"There are $N$ trampolines on a two-dimensional planar town where Takahashi lives. The $i$\\-th trampoline is located at the point $(x_i, y_i)$ and has a power of $P_i$. Takahashi's jumping ability is denoted by $S$. Initially, $S=0$. Every time Takahashi trains, $S$ increases by $1$.\nTakahashi can jump from the $i$\\-th to the $j$\\-th trampoline if and only if:\n\n*   $P_iS\\geq |x_i - x_j| +|y_i - y_j|$.\n\nTakahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps.\nAt least how many times does he need to train to achieve his objective?\n\n## Constraints\n\n*   $2 \\leq N \\leq 200$\n*   $-10^9 \\leq x_i,y_i \\leq 10^9$\n*   $1 \\leq P_i \\leq 10^9$\n*   $(x_i, y_i) \\neq (x_j,y_j)\\ (i\\neq j)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$x_1$ $y_1$ $P_1$\n$\\vdots$\n$x_N$ $y_N$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc257_d","tags":[],"sample_group":[["4\n-10 0 1\n0 0 5\n10 0 1\n11 0 1","2\n\nIf he trains twice, $S=2$, in which case he can reach any trampoline from the $2$\\-nd one.\nFor example, he can reach the $4$\\-th trampoline as follows.\n\n*   Jump from the $2$\\-nd to the $3$\\-rd trampoline. (Since $P_2 S = 10$ and $|x_2-x_3| + |y_2-y_3| = 10$, it holds that $P_2 S \\geq |x_2-x_3| + |y_2-y_3|$.)\n    \n*   Jump from the $3$\\-rd to the $4$\\-th trampoline. (Since $P_3 S = 2$ and $|x_3-x_4| + |y_3-y_4| = 1$, it holds that $P_3 S \\geq |x_3-x_4| + |y_3-y_4|$.)"],["7\n20 31 1\n13 4 3\n-10 -15 2\n34 26 5\n-2 39 4\n0 -50 1\n5 -20 2","18"]],"created_at":"2026-03-03 11:01:14"}}