题目描述

在一片神秘的古老遗迹中 , 勇敢的探险家小 $\rm S$ 发现了 $\rm N$ 个神奇的宝箱

每个宝箱都蕴含着独特的魔力 , 其魔力可由 $\rm A, B, C$ 三个属性表示

现在小 $\rm S$ 面临着一个艰难的抉择：对于每个宝箱 , 他仅能从中选取一种魔力属性值 , 可以是 $\rm A$ 属性 , 也可以是 $\rm B$ 属性 , 或者是 $\rm C$ 属性

根据古老的传说 , 为了唤醒遗迹深处的神秘力量 , 小 $\rm S$ 必须按照特定的数量挑选不同的魔力属性值

具体而言 , 需要挑选出 $\rm X$ 个 $\rm A$ 属性值、 $\rm Y$ 个 $\rm B$ 属性值以及 $\rm Z$ 个 $\rm C$ 属性值 , 并且满足 $\rm X + Y + Z = N$

不同的挑选组合将带来截然不同的魔力价值总和

你的任务就是找出能够使魔力价值总和达到最大的挑选方案 , 并求出这个最大价值是多少

输入格式

第一行输入四个空格分隔整数 $\rm N, X, Y, Z$

接下来 $\rm N$ 行 , 第 $\rm i+1$ 行输入三个空格分隔的整数 $\rm A_i, B_i, C_i$ , 表示第 $\rm i$ 个宝箱的三种魔力属性

输出一个整数表示答案

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

6000000000

对于前 $10\%$ 的数据 $\rm 1 \leq N \leq 10$

对于前 $20\%$ 的数据 $\rm 1 \leq N \leq 50$

对于前 $40\%$ 的数据 $\rm 1 \leq N \leq 500$

对于另外 $15\%$ 的数据 $\rm 1 \leq A_i, B_i, C_i \leq 2$

对于 $100\%$ 的数据 $\rm \rm 1 \leq N \leq 5000, 1 \leq A_i, B_i, C_i \leq 10^9 ,1 \leq X,Y,Z \leq N$

附加文件：ex_data.zip