#P18321. Ticket Revenue Maximization

Ticket Revenue Maximization

Ticket Revenue Maximization

一场锦标赛有128支队伍,编号为 1,2,…,1281,2,\ldots,128。对于任意 i<ji<j,队伍 jj 都比队伍 ii 强;两队比赛时,队伍 jj 一定获胜。

队伍 ii 有 PiP_i 名支持者,不同队伍的支持者互不重合。

比赛共有7轮。每一轮将仍在比赛中的队伍分成若干对,每支队伍恰好属于一对。每对队伍进行一场比赛,败者被淘汰,胜者晋级下一轮(如果还有下一轮)。

具体来说:

  • 第1轮,128支队伍进行64场比赛,64支获胜队伍晋级。
  • 第2轮,这64支队伍进行32场比赛。
  • 第3轮,这32支队伍进行16场比赛。
  • 依此类推,直到第7轮,只剩下两支队伍进行决赛。

越往后的轮次,门票越贵。第 rr 轮的每张门票价格为 rr。队伍 i,ji,j 在第 rr 轮比赛时,双方的每名支持者都会购买一张门票,所以这场比赛的收入为

r(Pi+Pj).r(P_i+P_j).

你负责安排每一轮的配对方式。求整个锦标赛能够取得的最大总收入。

输入格式

第一行包含整数 TT,表示测试用例数。

每组测试用例包含一行,给出128个整数 P1,P2,…,P128P_1,P_2,\ldots,P_{128}。

输出格式

对于每组测试用例,输出一行,包含最大总收入。

数据范围

  • 1≤T≤51\le T\le5;
  • 1≤Pi≤1091\le P_i\le10^9。

样例

输入

2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111
110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91
90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67
66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43
42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

输出

494
30318

说明

样例输入中的128个数因为原题文档的版面限制被拆成多行;实际测试中,每组的128个数位于一行。

第一组中,全部 Pi=1P_i=1,所以第 rr 轮的每场比赛收入都是 2r2r。各轮总收入依次为

128, 128, 96, 64, 40, 24, 14,128,\ 128,\ 96,\ 64,\ 40,\ 24,\ 14,

合计494。