卡丁车

文件读写

• 输入文件 car.in
• 输出文件 car.out

限制

• 1000ms
• 512MB

题目描述

小 Y 最近开始怀念童年了，他又开始玩自己小时候最爱的游戏 ——《跑跑卡丁车》 但是这个游戏现在新增了一个 强化 功能，这个功能可以让你的卡丁车各方面性能变强 卡丁车的强化一共分三个部件 —— 车胎，配重，氮气加速 但是强化显然需要氪金，小 Y 统计了一下系统赠送的新手礼包，一共有 n 个礼包，每个礼包都可以自选强化哪个部件，但是强化的费用是不一样的 对于第 i 个礼包：

1. 用于强化 车胎 需要花费 (a_i) 元
2. 用于强化 配重 需要花费 (b_i) 元
3. 用于强化 氮气加速 需要花费 (c_i) 元 现在小 Y 想用尽可能少的钱做到最好的强化效果，于是经过他的计算，他需要将这 n 个礼包中的 x 个用于强化 车胎， y 个用于强化 配重，z 个用于强化 氮气加速（保证 (n = x + y + z)） 现在小 Y 想知道，他最少花费多少钱？

数据范围

对于 (20\%) 的数据满足：(n \leq 15) 对于 (50\%) 的数据满足：(n \leq 100) 特别的，另外有 (20\%) 的数据满足：(z == 0) 对于 (100\%) 的数据满足：(1 \leq n \leq 5000, 0 \leq a_i,b_i,c_i \leq 10^9) 对于所有数据保证 (n = x + y + z)，且 (0 \leq x,y,z \leq n)

样例输入

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

样例输出

15

样例解释

将 5 号礼包用于强化 车胎，(1,2) 号礼包用于强化 配重，(3,4) 号礼包用于强化 氮气加速 一共花费 (4 + 4 + 3 + 3 + 1 = 15) 元

输入格式

输入第一行包含三个整数 (x,y,z)，分别表示需要用于三种配件强化的礼包数量 接下来输入 n 行，每行包含三个整数 (a_i,b_i,c_i)，含义如题

输出格式

输出一个整数，表示小 Y 的最小花费

国庆仿真模拟2