4329: C选家具(furniture)

内存限制：512 MB 时间限制：4.000 S
评测方式：文本比较 命题人：
提交：2 解决：1

题目描述

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

提示

### 样例一 #### 输入 ``` 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$ 。 | 测试点 | 数据范围 | | ----------- | ---------- | | $1\sim 4$ | $n\le 15$ | | $5\sim 10$ | $n\le 100$ | | $11\sim 14$ | $c=0$ | | $15\sim 20$ | 无限制 |

来源/分类

提交提交记录统计露一手!