← 返回题目列表

AtCoder · agc034_d

D. 曼哈顿最大匹配

中文机器翻译题面 查看原题

分数: 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