13981398 SUSTech Online Judge
Problem 1398 --Eating Breakfast

1398: Eating Breakfast

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 137  Solved: 28
[Submit][Status][Web Board]


As we all know, eating breakfast regularly is good for our health. As several new restaurants were opened in the campus, Miao decides that she will get up early and enjoy a nice breakfast every morning.

Noodles, porridge, bread, eggs... there are many kinds of food served in the morning. For each kind of food, there may be several dishes left, each contains different amount of sugar, fat and proteins. Of course, maybe for some kinds of food there are no dishes left, because Miao gets up late and the food of these kinds are sold out!

Miao will order some of the dishes left, and eat all of them without wasting. If Miao has totally uptake \(S\) grams of sugar, \(F\) grams of fat and \(P\) grams of proteins, she will have a happiness value of \(S\cdot F\cdot P\).

However, Miao would not order two dishes of the same kind, that is, she will order at most one dish for each kind of food.

Can you help Miao to calculate the maximum happiness value she can have?


The first line contains an integer \(n\), indicating the number of dishes left.

Each of the following \(n\) lines represents a dish of breakfast. The \(i\)-th of which contains four integers \(k_i, S_i, F_i, P_i\), indicating that the \(i\)-th dish belongs to the \(k_i\)-th kind of food and contains \(S_i\) grams of sugar, \(F_i\) grams of fat, and \(P_i\) grams of proteins.

\(1\leq n\leq 50;\)

\(\forall i\in [1,n]: 1\leq k_i\leq n; 1\leq S_i, F_i, P_i\leq 10^4;\)


Output the maximum happiness value Miao can have.

Sample Input

1 10 20 30
2 20 30 40
2 30 40 50
4 40 30 20

Sample Output



Miao will order the \(1,3,4\)-th dishes, and will get \((10+30+40)=80\) grams of sugar, \((20+40+30)=90\) grams of fat, and \((30+50+20)=100\) grams of proteins.