When I tried to understand her, I finally realized how much she had endured. Those things known and unknown, those displayed or hidden deep in her heart. Coincidences often form stories, just like Romeo and Juliet; only by falling in love with someone from a rival family can a legend be passed down through generations. And what about Zisuo and me? We would probably just be despised by the world for a "forbidden love between sisters." She was the first person I ever loved, and the only one. At first, I naively thought I would be her only one, but compared to me, she was more like a normal girl; even without a father, she still had the mother she loved deeply. Just like my own mother, their hearts were not filled with only me. So, someone like me was, in the end, just a fraction of their world. Since that is the case, being betrayed was only natural. Zisuo betrayed me — that is what I have always believed. Because she said her love for me would never end, but she broke her promise. She ended this relationship without even planting that blue spider lily that existed only in our imagination. Thinking about it, does she also feel that her mother betrayed her? Although I must also bear responsibility for her mother's betrayal. Thinking this way, being betrayed was my own fault. It seems I am the culprit behind this tragic state; as she said, would it have been better if I had died? Perhaps, yes! I peeked at Zisuo's diary and learned everything they had hidden from me. Then, I disguised myself as a pitiful victim, mourning the passing of my lover. I pretended not to know the reason for Zisuo's suicide, constantly hinting to myself to search for the truth of her death. However, when those diary entries, which should have been known only to the two of us, appeared before my eyes again and again with perfect accuracy, an unknown fear spread through my entire heart. They gripped my heart tightly, wanting it to stop beating. Whose prank it is has become irrelevant; whether it is Qingwei, Qianyu, or perhaps even Zisuo's spirit in heaven. In any case, I have had enough! I have had enough of my cowardly self, enough of the self that claimed to love her so much but dared to do nothing. Like the ending of the play at the Christmas party — where Juliet takes her own life with the sword in Romeo's hand — I raised the dagger in my hand. "It's a pity it's not the same one you used." "But, the final destination is always the same, isn't it?" ...... "Zisuo, I love you too!"
Description
Qianxun and Mianxue give you $n$ "books," each with four "attributes" $a_i, b_i, c_i, d_i$.
Formally, you need to partition the "books" into three non-empty sets $S_1, S_2, S_3$ to minimize the objective function $\mathbf{\Xi}$, defined as:
$$ \mathbf{\Xi}=\left(\max_{x=1}^3\max_{i\in S_x}a_i\right)\times\left(\sum_{x=1}^3\max_{i\in S_x}b_i\right)\times\left(\max_{x=1}^3\sum_{i\in S_x}c_i\right)\times\left(\sum_{x=1}^3\sum_{i\in S_x}d_i\right) $$
Find the minimum possible value of the objective function.
Input
The first line contains an integer $n$.
The next $n$ lines each contain four integers $a_i, b_i, c_i, d_i$, representing the "attributes" of the $i$-th book.
Output
A single line containing an integer $\mathbf{\Xi'}$, representing the minimum possible value of the objective function.
Examples
Input 1
4 1 220 29 1 1 195 20 1 1 200 9 11 1 180 30 1
Output 1
252000
Note 1
One optimal solution is: $S_1$ contains book $\{1\}$, $S_2$ contains books $\{2,3\}$, and $S_3$ contains book $\{4\}$. In this case, $\mathbf{\Xi}=\small1\times600\times30\times14=252000$.
Input 2
6 961 16 2 40 540 15 4 99 813 14 1 97 461 18 3 15 999 14 1 15 903 16 5 10
Output 2
81062856
Note 2
One optimal solution is: $S_1$ contains books $\{1,4\}$, $S_2$ contains books $\{2,3,5\}$, and $S_3$ contains book $\{6\}$. In this case, $\mathbf{\Xi}=\small999\times49\times6\times276=81062856$.
Input 3
See the provided files.
The answer may exceed the magnitude of $2^{64}$; it is recommended to use the __uint128_t data type to store and output the answer.
Input 4
See the provided files.
The data range for this sample is the same as the extreme data range, satisfying $n=600$, $\max c_i=70$, and $\sum c_i=1\times10^4$.
Subtasks
For all data, $1\leq n\leq600$, $1\leq a_i,b_i,c_i,d_i\leq10^9$, $\max c_i\leq70$, and $\sum c_i\leq1\times10^4$.