POLSKI SPOJ

Profesor Algobit jest twórcą… nowego projektu uczelnianego polegającego na produkcji wirtualnych monet Bitcoin'ów w celu zasilenia opł‚akanego budżetu uczelni. Do współpracy zaprosił‚ najlepszych pię™ciu programistów, między innymi Ciebie. Warunkiem koniecznym do wzię™cia udział‚u w projekcie jest posiadanie komputera osobistego, który bę™dzie wykonywał zlecenia skomplikowanych obliczeń, za co szkoła otrzyma wynagrodzenie w postaci bitmonet. Dodatkowo profesor otrzymał‚ pewien budżet, dzięki któremu bę™dzie można rozbudować‡ komputery programistów w celu zwię™kszenia mocy obliczeniowej komputerów i przyspieszeniu generowania profitów. Niestety pienię™dzy tych nie można podzielić‡ po równo mię™dzy programistów, ponieważ niektóre komputery lepiej reagują na rozbudowę™ i nawet niewielki wkł‚ad finansowy znacznie korzystniej wpływa na generowanie Bitcoin'ów niż inne. 

Znają…c wpł‚yw rozbudowy komputera na generowanie wirtualnych monet każdego programisty, określ ile maksymalnie można zwię™kszyć‡ produkcję Bitcoin'ów w cią…gu jednej doby mając do dyspozycji n tysięcy zł‚otych.

Wejś›cie

W pierwszym wierszu jedna liczba określająca liczbę zestawów danych (nie więcej niż 1000). 

W pierwszym wierszu każdego zestawu jedna liczba cał‚kowita  n określająca wielkość‡ budżetu (n ∈ [1..1000]).

Nastę™pnie pięć‡ wierszy, w każdym wierszu po n liczb cał‚kowitych (wartości te nie przekraczają 10⁷ oraz reprezentują ciąg niemalejący).

Jeś›li i-ta… liczba… danego wiersza ma wartość k, oznacza to, źe inwestują…c i tysięcy w komuter kolejnego programisty zwię™kszymy dobowo zysk o k Bitcoin'ów.

Wyjś›cie

Dla każdego zestawu jedna liczba określająca maksymalny zysk, jaki można otrzymać‡ inwestują…c n tysię™cy w komputery programistów.

Przykł‚ad

Wejście:
1
4
1 3 3 4
2 4 4 5
1 3 5 5
2 3 3 5
3 3 3 5

Wyjś›cie:
9

Wyjaś›nienie

Inwestują…c 2 tysią…ce w drugi komputer zwię™kszamy jego wydajność o 4, 

inwestują…c w komputer 4 i 5 zwię™kszamy wydajność odpowiednio o 2 i 3. 

W sumie: 4 + 2 + 3 = 9