{"problem":{"name":"M's Solution","description":{"content":"New AtCoder City has an infinite grid of streets, as follows: *   At the center of the city stands a clock tower. Let $(0, 0)$ be the coordinates of this point. *   A straight street, which we will c","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"m_solutions2020_e"},"statements":[{"statement_type":"Markdown","content":"New AtCoder City has an infinite grid of streets, as follows:\n\n*   At the center of the city stands a clock tower. Let $(0, 0)$ be the coordinates of this point.\n*   A straight street, which we will call _East-West Main Street_, runs east-west and passes the clock tower. It corresponds to the $x$\\-axis in the two-dimensional coordinate plane.\n*   There are also other infinitely many streets parallel to East-West Main Street, with a distance of $1$ between them. They correspond to the lines $\\ldots, y = -2, y = -1, y = 1, y = 2, \\ldots$ in the two-dimensional coordinate plane.\n*   A straight street, which we will call _North-South Main Street_, runs north-south and passes the clock tower. It corresponds to the $y$\\-axis in the two-dimensional coordinate plane.\n*   There are also other infinitely many streets parallel to North-South Main Street, with a distance of $1$ between them. They correspond to the lines $\\ldots, x = -2, x = -1, x = 1, x = 2, \\ldots$ in the two-dimensional coordinate plane.\n\nThere are $N$ residential areas in New AtCoder City. The $i$\\-th area is located at the intersection with the coordinates $(X_i, Y_i)$ and has a population of $P_i$. Each citizen in the city lives in one of these areas.\n**The city currently has only two railroads, stretching infinitely, one along East-West Main Street and the other along North-South Main Street.**  \nM-kun, the mayor, thinks that they are not enough for the commuters, so he decides to choose $K$ streets and build a railroad stretching infinitely along each of those streets.\nLet the _walking distance_ of each citizen be the distance from his/her residential area to the nearest railroad.  \nM-kun wants to build railroads so that the sum of the walking distances of all citizens, $S$, is minimized.\nFor each $K = 0, 1, 2, \\dots, N$, what is the minimum possible value of $S$ after building railroads?\n\n## Constraints\n\n*   $1 \\leq N \\leq 15$\n*   $-10 \\ 000 \\leq X_i \\leq 10 \\ 000$\n*   $-10 \\ 000 \\leq Y_i \\leq 10 \\ 000$\n*   $1 \\leq P_i \\leq 1 \\ 000 \\ 000$\n*   The locations of the $N$ residential areas, $(X_i, Y_i)$, are all distinct.\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$X_2$ $Y_2$ $P_2$\n $:$  $:$  $:$\n$X_N$ $Y_N$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"m_solutions2020_e","tags":[],"sample_group":[["3\n1 2 300\n3 3 600\n1 4 800","2900\n900\n0\n0\n\nWhen $K = 0$, the residents of Area $1$, $2$, and $3$ have to walk the distances of $1$, $3$, and $1$, respectively, to reach a railroad.  \nThus, the sum of the walking distances of all citizens, $S$, is $1 \\times 300 + 3 \\times 600 + 1 \\times 800 = 2900$.\nWhen $K = 1$, if we build a railroad along the street corresponding to the line $y = 4$ in the coordinate plane, the walking distances of the citizens of Area $1$, $2$, and $3$ become $1$, $1$, and $0$, respectively.  \nThen, $S = 1 \\times 300 + 1 \\times 600 + 0 \\times 800 = 900$.  \nWe have many other options for where we build the railroad, but none of them makes $S$ less than $900$.\nWhen $K = 2$, if we build a railroad along the street corresponding to the lines $x = 1$ and $x = 3$ in the coordinate plane, all citizens can reach a railroad with the walking distance of $0$, so $S = 0$. We can also have $S = 0$ when $K = 3$.\nThe figure below shows the optimal way to build railroads for the cases $K = 0, 1, 2$.  \nThe street painted blue represents the roads along which we build railroads.\n![image](https://img.atcoder.jp/m-solutions2020/fc274bed71a4c37706550fa083496d39.png)"],["5\n3 5 400\n5 3 700\n5 5 1000\n5 7 700\n7 5 400","13800\n1600\n0\n0\n0\n0\n\nThe figure below shows the optimal way to build railroads for the cases $K = 1, 2$.\n![image](https://img.atcoder.jp/m-solutions2020/7c6b7a31998a1c46fba4c0679b023822.png)"],["6\n2 5 1000\n5 2 1100\n5 5 1700\n-2 -5 900\n-5 -2 600\n-5 -5 2200","26700\n13900\n3200\n1200\n0\n0\n0\n\nThe figure below shows the optimal way to build railroads for the case $K = 3$.\n![image](https://img.atcoder.jp/m-solutions2020/0453fa9c2f02c3bd5d5f9e20d0e8e589.png)"],["8\n2 2 286017\n3 1 262355\n2 -2 213815\n1 -3 224435\n-2 -2 136860\n-3 -1 239338\n-2 2 217647\n-1 3 141903","2576709\n1569381\n868031\n605676\n366338\n141903\n0\n0\n0\n\nThe figure below shows the optimal way to build railroads for the case $K = 4$.\n![image](https://img.atcoder.jp/m-solutions2020/464ce76d1d7d72638eb372342f8386c5.png)"]],"created_at":"2026-03-03 11:01:14"}}