TopCoder

Thumb 1800
weyryafjnm;
ちょっと天井見てくるわ。。。

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

50.0% (7/14)

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

// Sample input 1
3 1 1 1
4 1 6
1 1 10
5 7 4

// 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

Sample Output

// Sample output 1
21

// 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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3 4 5 6
1 1000 524288 65536 1 2 3 4 5 6
2 1000 524288 65536 2 4 5 6
3 1000 524288 65536 2 4 5 6
4 1000 524288 65536 2 4 5 6
5 1000 524288 65536 2 4 5 6
6 1000 524288 65536 2 4 5 6
7 1000 524288 65536 3 6
8 1000 524288 65536 3 6
9 1000 524288 65536 3 6
10 1000 524288 65536 3 6
11 1000 524288 65536 3 6
12 1000 524288 65536 3 6
13 1000 524288 65536 3 6
14 1000 524288 65536 3 6
15 1000 524288 65536 3 6
16 1000 524288 65536 3 6
17 1000 524288 65536 3 6
18 1000 524288 65536 4 5 6
19 1000 524288 65536 4 5 6
20 1000 524288 65536 4 5 6
21 1000 524288 65536 4 5 6
22 1000 524288 65536 4 5 6
23 1000 524288 65536 4 5 6
24 1000 524288 65536 4 5 6
25 1000 524288 65536 5 6
26 1000 524288 65536 5 6
27 1000 524288 65536 5 6
28 1000 524288 65536 6
29 1000 524288 65536 6
30 1000 524288 65536 6
31 1000 524288 65536 6
32 1000 524288 65536 6