题目描述

在智亦珅泽教育的“星际物流与空间工程”实践课上，小珅老师作为导师，正带领学徒小泽处理一批紧急的教学物资。由于最近一批星际快递包裹被提前运走，学校的模拟货运码头上遗留了许多空集装箱，把原本宽敞的空地挤得水泄不通。为了腾出足够的场地搭建临时的跨星系通讯基站，小珅决定带领大家把这些废弃集装箱堆叠成一座稳固的高塔。

每个集装箱都可以看作一个长方体，其长、宽、高均为正整数。为了方便搬运和调整重心，集装箱可以通过旋转、翻转等操作，让任意一个面朝下放置。堆叠的规则非常严格：只有当一个集装箱（称为 A）的长、宽、高都不大于另一个集装箱（称为 B）的长、宽、高时，A 才能被稳稳地堆放在 B 的上方。（注意：这里的长、宽、高是相对于当前放置状态而言的，即底面已经选定的长和宽，以及垂直向上的高度）。

例如：有两个集装箱，长宽高分别是 $(30, 45, 20)$ 和 $(35, 35, 60)$。如果直接按原始尺寸放置，它们无法直接堆叠。但如果我们把第一个集装箱立起来，使其底面变为 $(30, 20)$，高度为 $45$（记为 $(30, 20, 45)$），此时它的长和高都小于第二个集装箱的底面边长，就可以将其放在第二个集装箱上了，堆叠出来的总高度为 $105$。

小珅给小泽下了个挑战：“小泽，给定码头上的 $n$ 个集装箱的原始尺寸，请你帮我计算出，通过最优的旋转和堆叠方式，我们最多能搭出多高的高塔？”

现在，请你帮助小泽编写程序，解决这个空间规划难题。

输入格式

输入第 $1$ 行，一个整数 $n$，表示集装箱的个数。

第 $2 \sim n+1$ 行，每行三个正整数，分别表示每个集装箱的长度、宽度和高度。集装箱可以翻转和选择任意面朝下。

输出格式

输出一行，一个非负整数，表示最终能堆叠出来的最大高度。

输入输出样例

输入 #1

3
50 45 20
95 37 53
45 23 12

输出 #1

190

输入 #2

2
38 25 45
76 35 3

输出 #2

76

输入 #3

6
7 11 17
7 17 11
11 7 17
11 17 7
17 7 11
17 11 7

输出 #3

102

说明/提示

• 样例 1 解释： 最优的堆叠顺序是从下往上依次为：

  • 第 $2$ 个集装箱放在底部，选取 $53 \times 37$ 的一面朝下，高度为 $95$。
  • 第 $1$ 个集装箱放在中间，选取 $45 \times 20$ 的一面朝下，高度为 $50$。
  • 第 $3$ 个集装箱放在顶部，选取 $23 \times 12$ 的一面朝下，高度为 $45$。 总高度为 $95 + 50 + 45 = 190$。

• 样例 3 解释： 这 $6$ 个集装箱实际上是同一个长方体的不同排列（$7, 11, 17$ 的全排列）。最优策略是选取其中一个维度作为固定的高度（这里选最大的 $17$），然后将剩下的两个维度（$7$ 和 $11$）作为底面，每次堆叠时底面保持不变。这样可以堆叠 $6$ 层，总高度为 $6 \times 17 = 102$。

数据范围

• 对于 $20\%$ 的数据，$n \le 10$。
• 对于 $50\%$ 的数据，$1 \le n \le 500$，且所有集装箱的高度相同（即任意一个维度固定，另外两个维度可任意组合）。
• 另有 $10\%$ 的数据，每个集装箱都是正方体（即长、宽、高相等）。
• 对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le \text{长度}, \text{宽度}, \text{高度} \le 100000$。

36
87238 41208 74637
83435 20727 8988
70530 27522 92046
42491 75199 62438
87906 54926 45120
8304 52061 90462
23102 56168 69233
67897 90455 61947
97298 29871 13681
3461 59762 82886
99002 71480 87244
26990 42594 37195
48914 61493 2552
74051 43968 36409
30311 67674 65909
51808 87790 31367
21576 35372 69244
72838 25500 14542
42318 82956 39916
81014 6984 88075
14872 39460 23121
27892 27350 9878
8468 51198 76333
38985 64288 63493
70621 89008 1162
17035 17242 61111
62378 70436 41172
98447 87330 74794
37531 34710 72857
22238 4943 57922
17235 88131 81645
97310 71513 72207
52455 75643 91461
75030 75674 38991
12991 44478 30124
47544 31530 72238

671545

187
24684 74542 78138
1260 98649 16791
29736 51634 41266
20994 73895 89988
55825 39763 37330
40671 6582 60746
85251 34543 17028
64757 16645 58749
47959 17088 42340
54710 84520 23778
2645 54447 11089
21444 64183 40867
72712 68128 98251
22874 59365 78773
75150 87797 48621
2215 26266 48641
37946 70790 10712
12429 52820 80097
2545 87241 35282
11766 90532 58524
93426 67909 37395
11793 45639 21943
1393 67172 38376
46884 55264 82766
23208 63375 37463
20154 28443 16096
77036 77955 27812
25009 51855 24332
79641 21881 23819
40856 60083 70455
61142 45593 16033
169 75902 49097
79598 42442 23228
33827 11722 45714
62195 3577 3425
90915 14992 64730
24667 43213 35099
72788 63336 4349
69377 88774 20082
22364 6998 12422
75870 69493 1269
63672 91829 80722
39854 41902 44907
12169 66434 27063
67905 3131 62538
99310 78432 91504
87042 37913 86189
39907 40086 93816
81709 33736 89109
85341 98988 83324
30991 56458 20060
66825 56735 18610
88127 10563 52764
27251 903 83756
52634 84502 66826
84149 64241 65113
81132 36925 66251
49995 21583 31238
4543 24246 31627
29258 60419 4264
23810 20380 92753
13279 64327 70467
22874 98575 50464
87074 84189 55899
50060 90040 51416
17683 97455 1489
70610 98274 66291
41671 54727 95526
80638 67127 666
14452 83577 72639
33701 20745 48400
27975 8558 20493
28244 57722 53676
41947 80528 33255
57703 75165 40412
5081 74232 27971
67111 89925 269
97343 56631 35881
74859 17678 13461
19927 49539 84829
79974 7993 57518
89570 56584 81760
51132 22977 93031
67349 93014 3395
45849 32031 76847
86744 47602 864
78899 32603 21034
2495 18978 46084
31114 99084 98600
29938 7900 95332
31119 14194 70288
68544 4451 7290
74811 7649 5646
95905 97331 4084
62776 27439 86138
77816 12818 10763
68916 75119 73831
30399 9182 55336
64816 84130 86937
17849 52394 93480
97373 44060 15836
77408 86924 10027
47071 50906 79380
78340 23111 57258
79341 22722 91045
93441 11316 88450
88120 96385 6831
18186 11226 40246
92409 81562 59116
22776 15208 57767
69324 15694 47311
69416 93599 45371
51393 52678 80612
57043 88956 50862
99137 91641 34234
92065 29366 4143
48410 8948 15549
20995 70321 52493
71891 48497 53016
69765 87896 84207
344 90265 19862
13800 53630 25105
66716 39866 68040
9785 95443 19335
76407 30942 4233
55402 32728 65049
1753 70320 5090
98115 87788 64927
40300 82141 63055
66079 54108 84910
32109 97566 56661
27250 39053 46100
2621 2900 76822
73188 19501 45659
82862 89201 99429
47042 82449 76891
87382 24346 97196
57317 72445 93913
49078 59589 38169
19213 50320 99169
95635 97055 47457
26677 40119 76396
50533 62189 55323
4650 29638 85064
94940 86016 73145
42492 37010 18681
39181 95090 96304
92290 20377 58093
82904 60976 58467
53574 35194 64231
44287 35874 71125
34444 52988 17712
81903 13913 90105
62412 65388 17919
89966 9072 58145
99703 18752 11383
11492 76820 4022
68942 62785 6159
26014 73249 14307
9257 69418 35533
58435 27238 17110
9965 53354 13780
80062 37993 90471
47791 25803 84764
3599 67463 39685
71155 98646 92774
76673 45987 33179
2544 61024 14085
31356 51697 93643
67882 74388 55637
40564 39885 69729
12263 76167 49608
93700 39476 45066
58691 61359 36476
60971 99559 30142
12292 17397 74700
22736 58500 437
82432 99514 26015
41991 52890 61311
97139 9671 35601
95150 87549 89365
10446 36681 64853
61352 24110 81332
73073 26467 66135
9845 5313 53029
54531 87131 7368
98712 36015 99819

1137316

433
72379 5224 12475
61845 83846 41914
94364 24776 21575
41146 87042 77636
65018 78057 30290
82749 68673 39158
53827 42645 882
11130 48862 36986
11134 451 67263
44180 22836 91452
30757 33702 56252
84687 62419 42035
33465 54503 29659
51268 8476 81439
41802 56297 12431
42048 71730 78042
22980 83729 7634
22382 49611 77476
64690 15052 39032
94487 71148 53639
92008 56174 27482
83303 90877 13946
42945 84335 74477
43749 54876 50828
84736 9450 54312
15607 45306 51606
34488 49724 1758
20399 22682 46500
35495 62155 92510
10754 22989 2840
66806 90061 68917
88075 30100 43755
9153 56262 11059
8393 49062 1505
198 92662 38703
71698 82525 84157
51403 9014 48737
35657 36945 38113
70493 13943 23756
22984 58800 53429
4556 45635 56240
75903 99674 94339
53173 18764 28996
72204 16537 95813
73311 4272 49005
85696 81121 32438
37116 97895 62934
57246 806 21716
84568 44842 8714
99670 61927 68416
78121 24235 83721
52163 86251 93187
63061 22260 24271
603 92507 73452
18311 8573 4409
18833 45221 62444
29927 65133 19629
61860 62080 90628
84164 17526 30685
22049 56840 78124
34175 82640 28645
8057 67658 93114
97067 35579 43476
31069 12835 29539
19335 59679 95020
25275 21192 98844
1474 90238 89687
28443 25172 7220
9208 90327 21344
17315 96032 95597
68924 11585 38948
17158 47677 49868
61385 21596 95265
30397 819 21412
7073 76147 10544
21721 92293 22150
43307 23662 13897
87529 16744 84958
35277 89122 62532
33516 61231 44755
52691 43293 14496
20414 86521 76491
68782 50576 84632
84002 92528 55157
30176 64442 13828
39651 95478 86341
60662 67678 36996
76074 40262 31924
22380 54272 364
12426 66417 66470
23782 58518 13675
20027 8896 6795
73110 68687 2229
94256 80070 87511
50735 15662 64500
94647 63015 78436
95459 58788 64960
11610 23210 35745
46260 95432 53109
63271 11427 52314
23950 45123 62047
67411 87238 54833
14656 52959 3270
44437 93018 63488
34370 7162 41625
50849 80091 7261
87530 42547 53618
6135 45856 25795
60251 72269 87171
34721 82018 2511
51633 60022 60477
4476 95995 15326
34989 35959 91121
99545 15387 33394
58237 83985 52544
80141 18042 8674
4581 89270 76940
43343 51211 43629
25259 36303 9628
30219 1225 73379
90085 13543 54124
85555 20506 32961
2810 42474 84882
60943 45526 67745
83960 87555 15357
79072 18163 60973
50700 46200 75854
16501 29333 90306
92716 42960 9660
6161 41918 47656
45015 42296 63716
39936 32007 63768
26326 66944 52898
77876 44491 44961
25647 23244 38333
21397 74370 88958
57626 66037 78769
73643 10502 52501
42238 70662 1396
85593 3717 22922
74361 65042 68327
4412 44976 65441
35563 87144 61562
48535 49528 36268
36729 71848 87413
16363 44150 56949
27991 57675 88410
62455 70864 84392
60319 60495 76976
82736 46618 49796
7281 54856 87245
55467 92635 46309
41792 76112 71071
46120 56433 34181
69916 36175 18010
51846 47672 47192
12838 74761 40659
10157 2190 89160
54156 48409 6069
73012 42847 55695
81840 43145 45676
51242 51052 41776
95345 16421 67682
69793 51773 41126
76495 79248 59622
16252 1251 54605
70820 55897 31247
17558 92024 66604
29490 86272 53987
32666 87889 59669
43374 2181 29248
93570 85515 44496
59330 60286 10555
50298 61520 21562
77988 9880 88328
74096 92218 17913
73680 50509 48516
90203 60428 42132
16803 87386 96777
54989 71416 59574
41644 36479 20661
519 12116 49496
87112 58935 47245
81849 77312 66602
93777 64000 79441
12071 35810 98376
53569 36726 2126
57529 91699 73744
95320 99991 82295
979 98287 82285
40336 6697 40860
2895 46224 53016
43084 23406 32866
1222 66775 97853
50129 43655 6979
25574 52112 52864
74645 33027 83283
76064 48718 81970
19642 84844 6788
66195 11065 92836
67080 2252 11740
34804 5205 4869
51542 94405 12212
75536 96184 17094
53031 46545 42263
35603 33146 99595
34797 32437 31850
97066 52433 48407
41278 6582 61172
8793 93951 51774
86828 91473 24604
7303 69905 62534
2753 91708 8448
70612 76780 12833
82784 71330 82038
84802 15092 46332
70537 71030 43146
16157 14837 64153
16806 1233 24920
90902 51515 19331
73626 76334 57528
82554 14011 28206
29720 62830 30370
41624 55052 4799
2427 45485 20392
93697 71871 82827
57010 20857 97489
47519 98214 96746
90746 13130 85451
52157 81812 80161
3275 27762 81792
91447 8043 65277
20215 62472 56809
5045 65501 74698
48007 49274 60929
95579 99068 65443
53921 28707 53153
1505 56093 44970
75841 5125 4728
62752 94516 75772
47232 84200 5701
19076 3957 73950
58832 70691 61438
74029 56759 3046
49943 19515 86230
52606 91598 42689
24153 55565 80398
55625 28793 42111
70339 85778 78758
36590 77185 95525
98520 69258 32142
50374 42812 66030
90801 87499 68912
20194 29465 34488
55124 85999 11824
38354 25606 79138
1731 3880 55096
25482 80788 90454
40438 28416 84171
64176 84251 61550
12469 88117 10320
94986 32552 79116
67303 78335 46674
83553 83348 16513
39099 56495 14233
16102 86446 93817
34251 56842 91861
5076 95457 69380
91504 9435 15502
76252 54042 36529
10930 40891 89115
66832 21321 17835
70122 18275 95082
78730 22786 16085
1109 64747 6521
4778 1021 84796
35167 21280 98796
69035 65027 97245
16812 55301 49312
37988 14346 90607
41697 58247 28224
75467 52496 78464
99663 64349 19966
93410 70148 70093
5988 55828 30238
9190 4950 75585
42973 49278 20877
32723 33359 18768
68263 85054 34981
15624 26620 43612
80070 44321 92870
87422 75750 71558
17342 69394 15607
30044 83002 60555
88790 6017 17443
63752 24014 26111
12447 92700 35067
34279 16384 26441
47894 93342 36531
48605 23675 22381
15174 54618 34254
31354 88970 77411
6441 32020 45995
53636 20907 82802
44035 84663 71220
63396 28604 43375
26206 39257 17692
59290 11162 10156
52462 30611 57563
27609 29260 36470
49166 95359 3597
88643 23953 20693
88127 59596 71978
26140 93579 2724
86494 75598 30338
46676 83810 24152
28185 57673 31796
57368 28060 61954
949 24885 50280
26401 3493 41392
93130 57596 61070
93232 26009 57076
28158 26371 32368
71519 65026 56006
96743 62164 50571
93025 52265 71077
94590 19463 49321
8916 29727 65279
67367 86091 25120
65172 90558 33489
59088 93620 50697
1196 62318 89362
61599 44120 32006
97827 71989 44258
17243 17699 28582
43150 3153 6246
34383 28859 74064
15741 82103 1722
66264 44413 19905
45551 33465 16021
9211 37525 98671
42459 86789 1010
15072 96917 44033
85376 94821 71921
30968 81801 76681
90731 92772 69923
45976 84751 32763
1620 55619 54881
19760 63214 21132
90244 28461 77041
91941 91163 10092
98514 85207 5831
7932 53724 49526
89646 95523 88499
72837 14478 11202
91341 40547 60625
29848 2220 25606
58679 20612 91565
44080 57434 30606
94043 23802 74898
63515 33234 47794
33383 10101 66892
63496 51131 72880
6999 31570 20269
12967 30611 10124
18531 53001 43261
36296 18663 20205
58225 94120 97483
54594 65038 69379
82043 71304 34508
87061 49215 25761
89126 28499 9828
48156 92907 36021
80888 14127 52434
79749 30140 99722
57695 15360 67417
74793 60439 76230
54108 47678 17445
27632 57900 45025
17257 16022 95626
33921 1965 6459
94757 28051 90541
55768 93539 60604
40665 90159 96494
91717 34675 68428
37679 49714 67436
93339 89147 32486
8092 67783 80129
42150 17002 88375
21019 14970 18323
70860 95832 23865
64140 87828 81942
74046 30544 4723
23875 27444 32784
16075 39941 92658
76526 26069 42291
95421 77000 42751
8289 72810 83183
65173 28046 30842
58215 89853 50699
56010 37175 96242
99071 92884 59257
81995 37179 86986
99062 5514 36152
83730 30042 56432
24676 44640 9583
58274 89024 76612
10036 64643 74132
5639 95867 45053
22587 41817 85555
39027 80844 65625
49662 69865 67753
80516 3838 22335
23752 73522 23279
4428 23976 71554
16722 50436 89775
97572 9784 50830
91515 38269 43313
99790 43885 69446
13336 26953 68241
70235 21926 1624
86915 87219 45552
36440 19301 45379
4308 40893 75019
29262 45598 47288
59123 67286 20235
85391 64009 44541
63429 38858 29586
67057 61323 42894
93014 20363 73942
10732 39611 68372
90319 43517 22228
53811 43244 82869

1683112