分数: 1200 点
问题陈述
Snuke 正在玩红色和蓝色的球,将它们放置在二维平面上。
首先,他表演了 N 放置红球的操作。在 i- 这些操作中,他放置了 RC_i 坐标处的红球 (RX_i,RY_i)。 随后,他又表演了另一场 N 放置蓝色球的操作。在 i- 这些操作中,他放置了 BC_i 坐标处的蓝色球 (BX_i,BY_i)。 放置的红球总数和放置的蓝球总数相等,即 \sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i。设该值为 S.
Snuke 现在将形成 S 成对的红色和蓝色球,以便每个球恰好属于一对。 让我们定义 分数 游戏的 坐标处一对红球 (rx, ry) 和坐标处的蓝色球 (bx, by) as |rx-bx| + |ry-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