该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

对于第 $i$ 个礼包：

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

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

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

输入格式

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

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

输出格式

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

数据范围

对于 $20\%$ 的数据满足：$n \leq 15$

对于 $50\%$ 的数据满足：$n \leq 200$

特别的，另外有 $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$ 元