2220 . 拿破崙改
TopCoder
Tags
Description
最近很流行一種叫作拿破崙的卡牌遊戲，今天，有人發明了一種新規則的拿破崙，叫作拿破崙改。
在拿破崙改當中，牌只有三種花色：黑桃、紅心和菱形，並且各有 $N$ 張，第 $i$ 張的這三種花色的牌上的點數分別是 $a_i,b_i,c_i$。接下來你要進行 $N$ 次選牌，第 $i$ 次選牌的時候，你要選擇第 $i$ 張黑桃、紅心或菱形牌的其中之一作為自己的手牌，剩下的牌則會被丟棄。
還有一個特殊的限制，你選擇的 $N$ 張牌中，黑桃、紅心和菱形牌必須分別恰有 $A,B,C$ 張。
這個遊戲如何決定勝負並不重要，你只想知道你的手牌的點數總和最大可以是多少。
測資限制
- $1 \leq A,B,C \leq N \leq 10^ 5$
- $A+B+C=N$
- $1 \leq a_i,b_i,c_i \leq 10^ 9$
Input Format
第一行有四個整數 $N,A,B,C$，分別表示每種花色各有 $N$ 張牌、三種花色的牌必須分別選恰 $A,B,C$ 張。
接下來有 $N$ 行，其中第 $i$ 行有三個整數 $a_i,b_i,c_i$，表示第 $i$ 張的黑桃、紅心、菱形牌的點數分別是多少。
Output Format
輸出一個整數，表示你的手牌的點數總和最大值。
Sample Input 1
3 1 1 1
4 1 6
1 1 10
5 7 4
4 1 6
1 1 10
5 7 4
Sample Output 1
21
Sample Input 2
6 3 2 1
1000000000 1 1
1000000000 1 1
1000000000 1 1
1 1000000000 1
1 1000000000 1
1 1 1000000000
1000000000 1 1
1000000000 1 1
1000000000 1 1
1 1000000000 1
1 1000000000 1
1 1 1000000000
Sample Output 2
6000000000
Hints
對於第一筆範測，選擇第 1 張黑桃、第 2 張菱形和第 3 張紅心牌，總點數是 $4+10+7=21$。
Problem Source
2021 師大附中校隊培訓 模擬競賽
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~6 | $N \le 18$ | 9 |
| 3 | 0~1, 7~17 | $C = 1$ | 17 |
| 4 | 0~6, 18~24 | $N \le 500$ | 19 |
| 5 | 0~6, 18~27 | $N \le 5000$ | 24 |
| 6 | 0~32 | 無額外限制 | 31 |