题目描述

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

首先，すぬけくん进行了 $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

输入

2
0 0 1
3 2 1
2 2 1
5 0 1

输出

8

样例 2

输入

3
0 0 1
2 2 1
0 0 2
1 1 1
1 1 1
3 3 2

输出

16

样例 3

输入

10
582463373 690528069 8
621230322 318051944 4
356524296 974059503 6
372751381 111542460 9
392867214 581476334 6
606955458 513028121 5
882201596 791660614 9
250465517 91918758 3
618624774 406956634 6
426294747 736401096 5
974896051 888765942 5
726682138 336960821 3
715144179 82444709 6
599055841 501257806 6
390484433 962747856 4
912334580 219343832 8
570458984 648862300 6
638017635 572157978 10
435958984 585073520 7
445612658 234265014 6

输出

45152033546

说明/提示

限制条件

• $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 翻译