AT_arc231_a [ARC231A] Two Dimensional Invader

You are a magic warrior on a two-dimensional plane, initially located at point $ (0, 0) $ . $ N $ events will now occur. In the $ i $ -th event ( $ 1 \leq i \leq N $ ), one monster appears at point $ (X_i, Y_i) $ , and you choose whether to defeat this monster with a sword or with magic. - If you choose to defeat the monster with a sword, you move to point $ (X_i, Y_i) $ . This incurs a cost equal to the square of the Euclidean distance between the point where you were located before moving and point $ (X_i, Y_i) $ . - If you choose to defeat the monster with magic, a cost of $ Z_i $ is incurred. In this case, you do not move. Find the minimum total cost eventually required. What is Euclidean distance? The Euclidean distance between point $ (a, b) $ and point $ (c, d) $ is defined as $ \sqrt{(a - c)^2 + (b - d)^2} $ .Solve $ T $ test cases per input file.

The input is given from Standard Input in the following format. Here, $ \mathrm{case}_i $ ( $ 1 \leq i \leq T $ ) denotes the $ i $ -th test case. > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ \vdots $ $ X_N $ $ Y_N $ $ Z_N $

Output $ T $ lines. The $ i $ -th line ( $ 1 \leq i \leq T $ ) should contain the answer for $ \mathrm{case}_i $ .

### Sample Explanation 1 - For the first test case, it is optimal to choose to defeat the monster with a sword in the first and third events, and to choose to defeat the monster with magic in the second event. Each event proceeds as follows. - In the first event, you move from point $ (0, 0) $ to point $ (0, 4) $ . This incurs a cost of $ 16 $ . - In the second event, a cost of $ 11 $ is incurred. - In the third event, you move from point $ (0, 4) $ to point $ (4, 5) $ . This incurs a cost of $ 17 $ . - The total cost eventually required is $ 16 + 11 + 17 = 44 $ . ### Constraints - $ 1 \leq T \leq 10 $ - $ 1 \leq N \leq 250\,000 $ - $ 0 \leq X_i < 500 $ ( $ 1 \leq i \leq N $ ) - $ 0 \leq Y_i < 500 $ ( $ 1 \leq i \leq N $ ) - $ 1 \leq Z_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ) - The sum of $ N $ over the $ T $ test cases is at most $ 250\,000 $ . - All input values are integers.