问题描述

Snuke正在玩红色和蓝色的球，在二维平面上放置它们。

首先，他进行了 $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$。

现在，Snuke要组成 $S$ 对红色和蓝色球，使得每个球恰好属于一对。我们定义一对红色球和蓝色球的 得分 为 $|rx-bx| + |ry-by|$，其中 $(rx, ry)$ 是红色球的坐标，$(bx, by)$ 是蓝色球的坐标。

Snuke想要最大化这些配对的得分之和。请帮助他找出得分之和的最大可能值。

约束条件

• $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$
• 输入中的所有值均为整数。

输入

输入的格式如下：

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

输出

输出得分之和的最大可能值。

示例输入1

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

示例输出1

8

如果我们将坐标为 $(0,0)$ 的红色球和坐标为 $(2,2)$ 的蓝色球配对，这对的得分是 $|0-2| + |0-2|=4$。然后，如果我们将坐标为 $(3,2)$ 的红色球和坐标为 $(5,0)$ 的蓝色球配对，这对的得分是 $|3-5| + |2-0|=4$。组成这两对得分的总和是 $8$，这是最大的结果。

示例输入2

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

示例输出2

16

Snuke可能在相同的坐标上进行了多次操作。

示例输入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

示例输出3

45152033546