[AGC018C] Coins
题意翻译
有 $x+y+z$ 个人,第 $i$ 个人有 $A_i$ 个金币,$B_i$ 个银币,$C_i$ 个铜币。
要选出 $x$ 个人获得其金币,选出 $y$ 个人获得其银币,选出 $z$ 个人获得其铜币。在不重复选某个人的情况下,最大化获得的币的总数。
$x+y+z\le 10 ^ 5$。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc018/tasks/agc018_c
$ 1 $ から $ X+Y+Z $ までの番号のついた、$ X+Y+Z $ 人の人がいます。 人 $ i $ は、金のコインを $ A_i $ 枚、銀のコインを $ B_i $ 枚、銅のコインを $ C_i $ 枚持っています。
すぬけ君は、彼らのうち $ X $ 人から金のコイン、$ Y $ 人から銀のコイン、$ Z $ 人から銅のコインをもらおうと考えています。 どの人からも、$ 2 $ 種類以上のコインをもらうことはできません。 また、どの人も、指定された色のコインをすべてあなたに渡してくれます。
すぬけ君は、最終的に持っている全ての色のコインの枚数の合計を最大化したいです。 すぬけ君が最終的に持っている全ての色のコインの枚数の合計の最大値を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ 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
输入样例 #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
说明
### 制約
- $ 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 $
### Sample Explanation 1
人 $ 1 $ から銀のコインを、人 $ 2 $ から銀のコインを、人 $ 3 $ から銅のコインを、人 $ 4 $ から金のコインをもらうと、 コインの枚数の合計は、$ 4+2+7+5=18 $ になります。 $ 19 $ 枚以上のコインを得る方法はないので、この例の答えは $ 18 $ になります。