AT_agc034_d.[AGC034D] Manhattan Max Matching

すぬけくん在二维平面上摆放了红球和蓝球进行游戏。

首先，すぬけくん进行了 $N$ 次放置红球的操作。第 $i$ 次操作时，在坐标 $(RX_i, RY_i)$ 处放置了 $RC_i$ 个红球。接着，すぬけくん又进行了 $N$ 次放置蓝球的操作。第 $i$ 次操作时，在坐标 $(BX_i, BY_i)$ 处放置了 $BC_i$ 个蓝球。这里，すぬけくん放置的红球总数与蓝球总数相等。也就是说，$\sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i$。以下将该值记作 $S$。

接下来，すぬけくん打算将所有红球和蓝球两两配对，共组成 $S$ 对。每个球恰好属于一个配对。对于坐标 $(rx, ry)$ 的红球和坐标 $(bx, by)$ 的蓝球组成的配对，其得分定义为 $|rx-bx| + |ry-by|$。

すぬけくん希望最大化所有配对得分的总和。请帮助すぬけくん求出配对得分总和的最大值。

输入以如下格式从标准输入读入。

$N$ $RX_1$ $RY_1$ $RC_1$ $RX_2$ $RY_2$ $RC_2$ $\cdots$ $RX_N$ $RY_N$ $RC_N$ $BX_1$ $BY_1$ $BC_1$ $BX_2$ $BY_2$ $BC_2$ $\cdots$ $BX_N$ $BY_N$ $BC_N$

输出配对得分总和的最大值。

限制条件

• $1 \leq N \leq 1000$
• $0 \leq RX_i, RY_i, BX_i, BY_i \leq 10^9$
• $1 \leq RC_i, BC_i \leq 10$
• $\sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i$
• 所有输入值均为整数。

样例解释 1

将坐标 $(0,0)$ 的红球与坐标 $(2,2)$ 的蓝球配对时，得分为 $|0-2| + |0-2| = 4$。将坐标 $(3,2)$ 的红球与坐标 $(5,0)$ 的蓝球配对时，得分为 $|3-5| + |2-0| = 4$。这两组配对的得分总和为 $8$，且这是最大值。

样例解释 2

可以在同一坐标多次进行操作。

由 ChatGPT 4.1 翻译