Sparing w Programowaniu Zespołowym Politechnika Poznańska, 13.03.2004

Opis

Często, gdy nie jesteśmy pewni własnych możliwości żołądkowych, zdarza się zamawiać jedną pizzę na dwie osoby. Pizza zostaje przywieziona i pojawia się następujący (często niewypowiedziany) problem - kto zje który z kawałków (kawałki pizzy mają z reguły różną wielkość, a każdy chciałby zjeść jak największą, a raczej jak najcięższą, część pizzy).

Przywieziona pizza jest okrągła. Obie jedzące ją osoby (nazwijmy je sobie A i B) są gorącymi zwolennikami tradycyjnego sposobu jedzenia pizzy i jego będą się trzymać - tj. można brać tylko te kawałki pizzy, które stykały się z tymi już wziętymi (oczywiście za wyjątkiem samego początku, kiedy to osoba biorąca pierwszy kawałek może wybierać swobodnie). Każdy kawałek może być jedzony w różnym tempie, w zależności od jego wielkości. Dla uproszczenia przyjmijmy, że czas jedzenia kawałka jest proporcjonalny do jego ciężaru oraz że A i B mają identyczne tempo spożywania. Kiedy jedna osoba skończy jeść kawałek podczas gdy druga ciągle konsumuje swój, to może wziąć kolejny, a wręcz musi go wziąć od razu, by nie wzbudzić podejrzeń "przeciwnika" (może zdarzyć się tak, że jedna osoba zje kilka kawałków w czasie gdy druga osoba będzie męczyć jeden). Problem robi się dopiero w sytuacji gdy obie osoby będą chciały sięgnąć po nowy kawałek równocześnie. W takiej sytuacji pierwszeństwo przyznawane jest naprzemiennie, tzn. gdy w przypadku jakiegoś "remisu" pierwszeństwo wyboru miał A, to w momencie nastąpienia kolejnego remisu pierwszeństwo przypadnie B, a jeszcze kolejnego to znów A, itd. Oczywiście pierwszy taki remis zachodzi już na samym początku - w tej sytuacji pierwszeństwo ma A.

Zadanie

Mając dane ciężary kawałków należy określić ile łącznie gramów pizzy zje osoba A, przy założeniu że obie osoby dążą do maksymalizacji zjedzonego ciężaru i obie trzymają się optymalnej strategii.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (1 ≤ D ≤ 30), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu danych znajduje się jedna liczba całkowita N (1 ≤ N ≤ 100), oznaczająca liczbę kawałków na jakie podzielona jest pizza. W drugim wierszu zestawu znajduje się ciąg N liczb całkowitych: W₁, W₂, ..., W_N (1 ≤ W_i ≤ 100, dla i = 1..N). W_i oznacza ciężar i-tego kawałka pizzy w gramach. Dla i = 2..N–1 kawałek i-ty sąsiaduje z kawałkami i–1 oraz i+1; z kolei kawałek 1-szy sąsiaduje z 2-gim oraz N-tym, a N-ty z 1-szym oraz (N–1)-szym.

Specyfikacja wyjścia

Dla każdego zestawu danych należy wypisać jeden wiersz zawierający dokładnie jedną liczbę całkowitą, oznaczającą maksymalny możliwy ciężar pizzy (w gramach) jaką może zjeść osoba A, przy założeniu optymalności posunięć obu osób.

Przykład

2
4
1 2 4 8
3
1 1 1

8
1