{"problem":{"name":"Manhattan Max Matching","description":{"content":"Snuke is playing with red and blue balls, placing them on a two-dimensional plane. First, he performed $N$ operations to place red balls. In the $i$\\-th of these operations, he placed $RC_i$ red balls","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc034_d"},"statements":[{"statement_type":"Markdown","content":"Snuke is playing with red and blue balls, placing them on a two-dimensional plane.\nFirst, he performed $N$ operations to place red balls. In the $i$\\-th of these operations, he placed $RC_i$ red balls at coordinates $(RX_i,RY_i)$. Then, he performed another $N$ operations to place blue balls. In the $i$\\-th of these operations, he placed $BC_i$ blue balls at coordinates $(BX_i,BY_i)$. The total number of red balls placed and the total number of blue balls placed are equal, that is, $\\sum_{i=1}^{N} RC_i = \\sum_{i=1}^{N} BC_i$. Let this value be $S$.\nSnuke will now form $S$ pairs of red and blue balls so that every ball belongs to exactly one pair. Let us define the _score_ of a pair of a red ball at coordinates $(rx, ry)$ and a blue ball at coordinates $(bx, by)$ as $|rx-bx| + |ry-by|$.\nSnuke wants to maximize the sum of the scores of the pairs. Help him by finding the maximum possible sum of the scores of the pairs.\n\n## Constraints\n\n*   $1 \\leq N \\leq 1000$\n*   $0 \\leq RX_i,RY_i,BX_i,BY_i \\leq 10^9$\n*   $1 \\leq RC_i,BC_i \\leq 10$\n*   $\\sum_{i=1}^{N} RC_i = \\sum_{i=1}^{N} BC_i$\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$RX_1$ $RY_1$ $RC_1$\n$RX_2$ $RY_2$ $RC_2$\n$\\vdots$\n$RX_N$ $RY_N$ $RC_N$\n$BX_1$ $BY_1$ $BC_1$\n$BX_2$ $BY_2$ $BC_2$\n$\\vdots$\n$BX_N$ $BY_N$ $BC_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc034_d","tags":[],"sample_group":[["2\n0 0 1\n3 2 1\n2 2 1\n5 0 1","8\n\nIf we pair the red ball at coordinates $(0,0)$ and the blue ball at coordinates $(2,2)$, the score of this pair is $|0-2| + |0-2|=4$. Then, if we pair the red ball at coordinates $(3,2)$ and the blue ball at coordinates $(5,0)$, the score of this pair is $|3-5| + |2-0|=4$. Making these two pairs results in the total score of $8$, which is the maximum result."],["3\n0 0 1\n2 2 1\n0 0 2\n1 1 1\n1 1 1\n3 3 2","16\n\nSnuke may have performed multiple operations at the same coordinates."],["10\n582463373 690528069 8\n621230322 318051944 4\n356524296 974059503 6\n372751381 111542460 9\n392867214 581476334 6\n606955458 513028121 5\n882201596 791660614 9\n250465517 91918758 3\n618624774 406956634 6\n426294747 736401096 5\n974896051 888765942 5\n726682138 336960821 3\n715144179 82444709 6\n599055841 501257806 6\n390484433 962747856 4\n912334580 219343832 8\n570458984 648862300 6\n638017635 572157978 10\n435958984 585073520 7\n445612658 234265014 6","45152033546"]],"created_at":"2026-03-03 11:01:14"}}