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.

题目描述

张老师最近开始怀念童年了，他又开始玩自己小时候最爱的游戏——《跑跑卡丁车》

但是这个游戏现在新增了一个 强化 功能，这个功能可以让你的卡丁车各方面性能变强

卡丁车的强化一共分三个部件——车胎，配重，氮气加速

但是强化显然需要氪金，张老师统计了一下系统赠送的新手礼包，一共有 $n$ 个礼包，每个礼包都可以自选强化哪个部件，但是强化的费用是不一样的

对于第 $i$ 个礼包：

1. 用于强化 车胎 需要花费 $a_i$ 元
2. 用于强化 配重 需要花费 $b_i$ 元
3. 用于强化 氮气加速 需要花费 $c_i$ 元

现在张老师想用尽可能少的钱做到最好的强化效果，于是经过他的计算，他需要将这 n 个礼包中的 $x$ 个用于强化 车胎， $y$ 个用于强化 配重，$z$ 个用于强化 氮气加速（保证 $n = x + y + z$）

现在张老师想知道，他最少花费多少钱？

输入格式

输入第一行包含三个整数 $x,y,z$，分别表示需要用于三种配件强化的礼包数量

礼包总数 $n = x+y+z$，输入中不会单独给出 $n$，需要你自行计算

接下来输入 $n$ 行，每行包含三个整数 $a_i,b_i,c_i$，含义如题

输出格式

输出一个整数，表示张老师的最小花费

样例 1

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$ 元

数据范围

对于 $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$