408559: GYM103186 B 小 A 的卡牌游戏

小 A 最近沉迷于一款名为 Hearthverse 的卡牌游戏。在这款游戏中，卡被分为了三个种类（随从、法术和魔法阵），在组卡时，这款游戏严格规定了卡组中每种卡牌的数量，具体来说，一副 $$$n$$$ 张卡的卡组需要包含恰好 $$$a$$$ 张随从卡， $$$b$$$ 张法术卡和 $$$c$$$ 张魔法阵卡，并且 $$$a + b + c = n$$$。

在游戏中，有一个叫做 "3pick" 的组卡竞技方式，游戏会给出 $$$n$$$ 次三选一的机会，三张卡分别来自三个种类。每次玩家需要从三张卡中选出一张卡加入自己的卡组。为了使卡组强度尽量高，小 A 给每张卡设定了一个强度值，而卡组的强度就是所有卡强度值的和，他希望他最后组出的卡组的强度可以尽量高。

第一行有四个整数 $$$n, a, b, c$$$ ($$$1\leq a, b, c\leq n \leq 5000, a+ b + c = n$$$)，分别表示卡组的总卡数与每种种类的卡的张数要求。

接下来 $$$n$$$ 行，每行代表一次 "3pick" 的机会，第 $$$i$$$ 行有三个整数 $$$a_i,b_i,c_i$$$ ($$$1 \leq a_i,b_i,c_i \leq 10^9$$$) 分别表示这一次选择中随从卡、法术卡和魔法阵卡的强度值。

在一行输出一个整数，表示 小 A 能组出的卡组的最大强度值。

3 1 1 1
4 1 6
1 1 10
5 7 4

21

6 3 2 1
1000000000 1 1
1000000000 1 1
1000000000 1 1
1 1000000000 1
1 1000000000 1
1 1 1000000000

6000000000