题目背景

当我尝试着去理解她时，我才知道她究竟承受了多少.
那些被人知晓的、和不为人知的，表现出来的、或是藏在心底的.
巧合往往才能构成故事，就像罗密欧和朱丽叶那样，爱上身为世仇的对方才会有之后的世代流传.
那我和紫娑呢？大概只会因为“姐妹间的禁忌之恋”被世人所唾弃吧.
她是我爱上的第一个人，也是唯一的一个.
起初，我也天真地以为我会是她的唯一，但相比起我来，她则更像一个正常的女孩，即使没有爸爸，她还有她深爱着的妈妈.
就如我的母亲一样，她们的心里并非只有我一个人.
所以，像我这样的人，到头来也不过只是其中的几分之一.
既然如此，被背叛也就是理所当然的了.
紫娑背叛了我 —— 我一直是这样认为.
因为她说过对我的爱会一直不结束，但是她食言了，她还没有为我种出那片存于想象中的蓝色彼岸花，就擅自结束了这段感情.
这么说来，她会不会也觉得她的妈妈背叛了她呢？虽然我也要为她妈妈的背叛负上责任.
这样想的话，被背叛也就是我自作自受了.
似乎我才是造成现在这副惨态的元凶，就像她说的，是不是如果我死了就好了？
也许，是的！
我偷看了紫娑的日记，知晓了她们向我隐藏起的一切.
然后，把自己伪装成受害者的可怜模样，缅怀着爱人的离世.
我假装不知道自己已经知晓紫娑自尽的理由，不断地暗示着自己去寻找她死去的真相.
可是，当那些只应该是我们两个人才知道的日记内容一次次准确无误地出现在我的眼前时，不知名的恐惧蔓延上了整颗心脏.
它们死死地箍着我的心，想让它停止跃动.
究竟是谁的恶作剧已经变得无关紧要了，晴唯也好，浅语也罢，或者是紫娑的在天之灵也说不定.
总之，我已经受够了！
我受够了胆小的自己，受够了明明嘴上说着多么爱她、却什么都不敢做的自己.
我像圣诞晚会时的那出戏的结局 —— 朱丽叶用罗密欧手中的剑自刎殉情一样，举起了手中的匕首.
「可惜，和你用的不是同一把.」
「不过，最终的归处总是同一个吧.」
......
「紫娑，我也爱你！」

题目描述

本题大致为 #2389. 「SHOI2007」书柜的尺寸 加强版，为减少无意义提交，题意略有不同.

千寻、眠雪给了你 $n$ 个「书本」，每个「书本」有四个「属性」$a_i,b_i,c_i,d_i$.

形式化地来说，你需要将「书本」划分为三个非空集合 $S_1,S_2,S_3$，最小化目标函数 $\mathbf{\Xi}$，定义为：

$$\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) $$

求出目标函数的最小可能值.

输入格式

第一行，一个整数 $n$.

之后 $n$ 行，每行四个整数 $a_i,b_i,c_i,d_i$，表示第 $i$ 本书的「属性」.

输出格式

仅一行，一个整数 $\mathbf{\Xi'}$，表示目标函数的最小可能值.

4
1 220 29 1
1 195 20 1
1 200 9 11
1 180 30 1

252000

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

81062856

见题目文件中的 "sample3.in"

2494166855990476206207227700

见题目文件中的 "sample4.in"

380667701560120511233843739248488

数据范围与提示

对于所有数据，$1\leq n\leq600$，$1\leq a_i,b_i,c_i,d_i\leq10^9$，$\max c_i\leq70$，$\sum c_i\leq1\times10^4$.