Sweet Voice

Posted on 21/01/2019, in Career.

infoCredit to Ziyi

Question Description

Keke has a brother named Hehe. Their voices are very sweet, but they don’t like to bark unless you buy dog biscuits for them. Different kinds of biscuits can make them bark different times, the same biscuit has different effect on Keke and Hehe. If you only give dog biscuits to one of them or give them different biscuits, one will be unhappy and bite you. So when you buy dog biscuits, you have to buy two pieces of same type (actually there are only 2 pieces for each type of biscuits). Calculate the minimum cost to make the two dogs speak no less than your requirements.

Input format

The first line of the input file is 3 integers $n$, $k$, $h$. $n$ is the types of dog biscuits, $h$ is the times Keke would bark, $n$ is the times Hehe would bark. Next $n$ lines represent $n$ biscuit where each line has three integers $s_i$, $b_i$, $c_i$: $s_i$ is the times Keke bark; $b_i$ is the number of times Hehe bark; and $c_i$ is the price. We also have the following constraints for the input: $1\leq n \leq 1000$, $1\leq s$, $b\leq 50$, $0\leq s_i, b_i, c_i \leq 2147483647$.

Output format

The output file has only one integer, the minimum cost to meet your requirements.


Sample input

5 5 10 12 5
2 4 10 37 8
1 11 36 6 0 18

Sample output


Time Limit


Function signature

int minCost(int n, int k, int h, const vector<vector<int>> & biscuits);