You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

C选家具(furniture)

题目描述

小 D 最近搬家了，需要购置 $a$ 台家电、$b$ 件家具和 $c$ 个装饰。他来到了商场，商场正好在举行优惠大酬宾，每家店铺都推出了一系列活动。

一共有 $n=a+b+c$ 家店铺，活动期间在第 $i$ 家店铺购买家电只需要 $a_i$ 元一台，购买家具只需要 $b_i$ 元一件，购买装饰只需要 $c_i$ 元一个，但每一家店铺限定每位顾客最多只能购买一种类型的物品一个。

小 D 希望在满足采购需求的情况下总花费最少，你能帮帮他求出最小花费吗？

输入格式

一共一行四个整数 $n,a,b,c$ ，分别表示店铺的数量和小 D 需求的每一种类型物品的数量。

接下来一共 $n$ 行，每行三个非负整数 $a_i,b_i,c_i$，含义如题。

输出格式

输出共一行一个整数，表示小 D 的最小花费。

样例一

输入

5 1 2 2
6 4 3
8 4 7
2 7 3
8 10 3
1 7 2

输出

15

样例解释

在第一，二家店各买一台家具，在第三、四家店各买一个装饰，在第五家店买一件家电。

一个花费 $4+4+3+3+1=15$ 元。

数据范围

对于所有数据 $n,a,b,c\le 5000,a_i,b_i,c_i\le 10^9$ ，保证 $n=a+b+c$ 。