{"raw_statement":[{"iden":"problem statement","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?"},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"4\n-10 0 1\n0 0 5\n10 0 1\n11 0 1"},{"iden":"sample output 1","content":"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|$.)"},{"iden":"sample input 2","content":"7\n20 31 1\n13 4 3\n-10 -15 2\n34 26 5\n-2 39 4\n0 -50 1\n5 -20 2"},{"iden":"sample output 2","content":"18"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}