题目描述

从前有$\red{2}$只狗，大的叫大狗，小的叫小狗，它们$\red{2}$个合起来就是狗儿们，使用英语的人把它们写作Girlman，传来传去，到最后大家决定叫它们格尔曼。它们的叫声很特别，但是它们十分吝啬它们的叫声，你为了听到它们的叫声，决定买狗饼干送给它们吃，不同种类的饼干能让它们叫的次数不一样，同一块饼干对于大小格尔曼的效果也不一样。它们很贪婪，如果你只给其中一只格尔曼吃狗饼干或者给两只格尔曼吃的不一样，有一只就会不高兴，因此你买狗饼干的时候总要两块两块地买，而且现在每类饼干也只有$\red{2}$块（想要多的也没得）。现在不是流行节约型社会吗？因此你也不能浪费，你要求的是在满足你要听格尔曼叫声次数要求的情况（两只格尔曼实际叫的次数都不小于你的要求即可）下的最小花费是多少。

输入格式

输入文件的第一行为$\red{3}$个整数$\red{n}$、$\red{s}$、$\red{b}$，分别表示狗饼干的类数、你想听到的小格尔曼的叫声次数和大格尔曼的叫声次数，接下来有$\red{n}$行，第$\red{i+1}$行有$\red{3}$个整数$\red{si}$、$\red{bi}$、$\red{ci}$，分别表示第$\red{i}$类狗饼干能让小格尔曼叫的次数、能让大格尔曼叫的次数和该类饼干的单价。

输出格式

输出文件只有一个整数，为满足你的要求情况下的最小花费。

样例

输入样例

5 5 10
1 2 5
2 4 10
3 7 8
1 11 36
6 0 18

输出样例

36

提示

$\red{30\%}$的数据满足$\red{1≤n≤30}$；

$\red{100\%}$的数据满足$\red{≤n≤1000}$、$\red{1≤s}$,$\red{b≤50}$、$\red{0≤si}$ ,$\red{bi}$ ,$\red{ci≤2147483647}$,

保证一定有解。