Ling Qiu, Luna and Triple Backpack
题号:NC223900
时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 384 M,其他语言768 M
64bit IO Format: %lld

题目描述

Ling Qiu and Luna gives you an object series of n objects, each is indicated with four parameters a_i, b_i, c_i, d_i.

She will ask you to classify those objects to three non-empty classes, or sets S_1, S_2, S_3, in order to minimize a target function \Xi, which is calculated by the following:

\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_z} d_i \right)

By the time those objects have been classified, she will query the minimum value of \Xi that you have found, you will need to output the minimum value of the target function \Xi.

输入描述:

The first line contains one integer n \ (3 \leq n \leq 300).

The next n lines contain four integers a_i, b_i, c_i, d_i \ (1 \leq a_i, b_i, c_i, d_i \leq 10^9) each, the i-th line describes the i-th object.

Additionally, it is guaranteed that \max c_i \leq 35, \sum c_i \leq 5 \times 10^3.

It is virtuously hinted by the task author that the coding to this problem may be tedious and complicated.

输出描述:

The only line contains one integer \Xi', namely the minimum value of the target function \Xi.

Note that the integer \Xi' may reach or even exceed 2^{64}, so we recommend using the data type `__uint128_t`, expressing an 128-bit unsigned integer.
示例1

输入

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

输出

复制
252000
示例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

输出

复制
81062856
示例3

输入

复制
100
4289025 52 1 473208716
8961 95 2 159884571
243713 69038 35 124035444
68846593 30 2 281690976
794625 8 3 772722093
11265 6686 2 328409731
224702465 912 14 586355292
163073 159 5 664584076
79873 77 26 956926382
11451649 99792 35 115820350
7937 7351 8 698779396
645242113 5062 28 915758144
2633217 43 5 49348308
465481473 402 23 565272642
193025 22467 32 989648850
12801 97 23 754740796
139521537 92 1 838153786
6145 65 35 588996496
513 6997 1 181090038
1628929 8337 35 499984282
20737 2380 34 49507014
512618241 1133 32 370005793
235856641 33 17 550857178
24785665 31659 35 990570697
373687297 678 1 86653951
1281 83146 2 923917377
2049 64 34 692780503
140655361 55 9 949769137
684801 46 13 100247266
3073 357 1 141409862
108801 99374 2 191355999
769 767 28 689219060
151809 1741 32 755179823
2561 4931 29 6193759
494571777 6680 11 53928010
1829377 83285 1 641695725
7937 3 32 754726993
69889 8169 21 180335
64337665 88 22 111124115
5928193 5 1 4426102
16330241 780 3 116278575
157821953 8 14 593574641
1281 932 13 6387483
115713 32982 35 254346968
177409 10 31 365147434
45883905 90039 2 484298109
393618433 74765 2 489837348
769 7 33 557854007
16385 23 3 357844010
757370881 7247 13 452939225
1710337 868 16 645860219
4728065 3 14 873136368
103237121 6 24 618983438
185857 88281 4 644184765
224072705 6 15 969231013
189969153 5675 35 72431450
1537 73191 4 393279237
14337 2279 2 423690806
6401 34 35 566073868
1281 40345 35 995089408
2296065 580 3 323338798
239361 76 29 707151348
1793 57 34 306609099
257 5136 22 901216306
93697 5 1 299689739
2305 8626 31 49224082
23097857 10 33 174460153
4316417 19 5 144094727
9729 1040 14 663254573
1209857 725 2 737458440
1281 2 1 21467519
261687809 851 28 984257020
1281 70 29 493677852
1793 2281 33 169835442
19969 98 28 855401764
882968065 1177 2 707518629
37998593 6804 31 59314317
1281 9463 23 764649428
192769 26696 1 504453201
78737921 166 31 705583561
196244225 51 21 347110588
1297153 71 33 834101478
25075713 843 14 694385596
531697153 42189 35 245147662
1820417 32789 35 712655386
2305 88 33 203623526
10168577 70 1 457616017
109313 206 5 610336718
193367297 12995 1 433709669
1807105 2 11 263178886
8299265 139 35 192320918
769 6953 1 923968634
14337 84 28 115824569
149249 13169 29 331307522
33281 875 32 437462682
12488705 401 1 219291450
833537 255 14 459008341
2049 267 2 255398375
6332417 77521 2 121755446
24962817 38 24 330897854

输出

复制
2494166855990476206207227700

备注: