TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

76.2% (16/21)

Description

你,もも,解決了很多居民的煩惱之後,
他們推舉你出來選舉,
但是選舉並沒有那麼簡單,
並不是靠著老爸就可以。

而且這邊選制非常的特別,
是有很多基礎選區,中選區,大選區,加大選區,兩倍加大選區...構成的,
你發現不管在哪個地方,
只要贏得超過一半的支持就贏了,
你也發現,不管在哪,
總是奇數個選區,或者奇數個選民。

你想知道成為這邊的首領至少要拿到幾票。

Input Format

你發現你的野心越來越大,
所以你當上了二維空間的王就想當三維的王,
當了三維的王就想當四維的...

所以你有很多很多的選戰要打。
因此這題也是多筆測資,
第一個數字$N$代表接下來有幾筆測資。
接著測資的形式請參考Sample Input。
$N\le500$
單行長度不超過 16384,每個小選區的人數不超過10000。

Output Format

對於每筆測資輸出你最少要贏幾票。

Sample Input

3
[[123][4567][89]]
[[5][3][7][3][9]]
[[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]

Sample Output

107
7
175

Hints

每個成對[]代表一個選區
[[123][4567][89]]
代表裡面有三個小選區
你在這三個小選區贏了其中兩個(也就是超過一半)就可以稱王了
如果選擇[123]跟[89]那麼會是最佳解。
贏得[123]需要贏62票,[89]需要45票,
所以最少票數是107票。

Problem Source

Tocknicsu

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144