← 返回题目列表

AtCoder · agc018_c

C. 硬币

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

分数: 800 点

问题陈述

有 X+Y+Z 人,方便编号 1 通过 X+Y+Z。 人 i 有 A_i 金币, B_i 银币和 C_i 铜币。

Snuke 正在考虑从 X 那些人,银币来自 Y 的人和铜币来自 Z 人民。 一个人不可能获得两种或多种不同颜色的硬币。 另一方面,一个人将给出他/她所有由 Snuke 指定颜色的硬币。

Snuke 希望最大化他获得的所有颜色的硬币总数。 找出最大可能的硬币数量。

约束

  • 1 \leq X
  • 1 \leq Y
  • 1 \leq Z
  • X+Y+Z \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 1 \leq C_i \leq 10^9

输入

输入由标准输入按以下格式给出:

X Y Z
A_1 B_1 C_1
A_2 B_2 C_2
:
A_{X+Y+Z} B_{X+Y+Z} C_{X+Y+Z}

输出

打印他获得的所有颜色的硬币的最大可能总数。


示例输入 1

1 2 1
2 4 4
3 2 1
7 6 7
5 2 3

示例输出 1

18

从 Person 处获取银币 1,来自 Person 的银币 2,来自 Person 的铜币 3 和来自 Person 的金币 4。 在这种情况下,硬币总数将是 4+2+7+5=18。 不可能得到 19 或更多硬币,因此答案是 18.


示例输入 2

3 3 2
16 17 1
2 7 5
2 16 12
17 7 7
13 2 10
12 18 3
16 15 19
5 6 2

示例输出 2

110

示例输入 3

6 2 4
33189 87907 277349742
71616 46764 575306520
8801 53151 327161251
58589 4337 796697686
66854 17565 289910583
50598 35195 478112689
13919 88414 103962455
7953 69657 699253752
44255 98144 468443709
2332 42580 752437097
39752 19060 845062869
60126 74101 382963164

示例输出 3

3093929975