Prihlásenie Registrácia  

S - Súčet

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Deti sa veľmi rady hrajú s kartičkami. Majú niekoľko vlastných sád kartičiek, očíslovaných číslami 0 až 31. Vymysleli si novú hru. Na začiatku náhodne rozložia niekoľko kariet vedľa seba. V každom ťahu vždy dve susedné karty zamenia za jednu kartu, ktorej hodnota je súčet pôvodných dvoch (modulo 32, keďže majú iba takéto čísla). Tento ťah má hodnotu súčinu pôvodných hodnôt. Hrajú pokiaľ im už nezostane posledná kartička. Na konci hry spočítajú hodnoty všetkých ťahov.
Pomôžte im pre dané rozmiestnenie kartičiek určiť najvyšší možný celkový bodový zisk za celú hru.

Úloha

Pre danú postupnosť kariet určte maximálnu hodnotu bodov, ktoré môžu deti získať, ak budú zamienať susedné karty podľa pravidiel popísaných vyššie.

Vstup

V prvom riadku súboru sa nachádza jedno kladné celé číslo T udávajúce počet testovacích sád.
Pre každú testovaciu sadu nasledujú dva riadky. V prvom riadku je kladné celé číslo 1 ≤ N ≤ 100 udávajúce počet kartičiek. V druhom riadku nasleduje N nezáporných celých čísel 0 ≤ C ≤ 31, označujúcich hodnoty kartičiek v rade.

Výstup

Výstup obsahuje pre každú testovaciu sadu jeden riadok, obsahujúci jedno nezáporné celé číslo - maximálny bodový zisk pre zadanú postupnosť kartičiek.

Príklad

Vstup:

2
3
1 2 3
3
15 25 20 

Výstup:

11
695
V druhej sade máme dve možnosti: Buď najprv zameníme prvé dve karty, zostanú karty 8 a 20, čo bude 15*25+8*20 = 535 bodov. Alebo zameníme najprv posledné dve karty, zostanú 15 a 13, čo bude 25*20+15*13 = 695 bodov.