Кішкентай Көгілдір Балық Slay the Spire II ойынын ойнап отыр және «Үнсіз» (Silent) кейіпкерін таңдады.

Енді Кішкентай Көгілдір Балық «Шайқас досымен» (Battle Friend) шайқасуы керек. Бастапқыда Шайқас досының «У» (Poison) қабаттарының саны да, сіздің «Үдеткіш» (Accelerant) деңгейіңіз де $0$-ге тең. Келесі $n$ жүрістің әрқайсысында келесі оқиғалар ретімен орындалады:

1. «Өлімші у» (Deadly Poison) қолдану: Шайқас досының У қабаттарының санын $x_i$-ге арттыру.

2. «Үдеткішті» қолдану-қолданбауды таңдау: Үдеткіш деңгейіңізді $1$-ге арттыру немесе арттырмауды таңдау.

3. У әсерін іске қосу: сіздің Үдеткіш деңгейіңіз $t$ болсын, келесі оқиғаны $t$ рет қайталаңыз:

   • Шайқас досының У қабаттарының саны $x$ болсын. Егер $x > 0$ болса, Шайқас досына $x$ зақым келтіріп, У қабаттарының санын $1$-ге азайтыңыз; әйтпесе, егер $x = 0$ болса, ештеңе болмайды.

Ескерту: У қабаттары да, Үдеткіш деңгейі де жүрістер арасында сақталады және жойылмайды.

Кішкентай Көгілдір Балық осы $n$ жүріс ішінде Шайқас досына келтірілетін жалпы зақымды барынша арттырғысы келеді. Осы ең үлкен зақым мәнін шығарыңыз.

Кіріс деректер

Кіріс деректер бірнеше тест жиынтығынан тұрады. Бірінші жолда тест жиынтықтарының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жиынтығы үшін бірінші жолда бір бүтін сан $n$ ($1 \le n \le 5000$) берілген.

Екінші жолда әр жүрісте Шайқас досына қосылатын У қабаттарының санын білдіретін $n$ бүтін сан $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$) берілген.

Барлық тест жиынтықтары бойынша $n$ қосындысы $10^6$-нен аспайтынына және барлық тест жиынтықтары бойынша $n^2$ қосындысы $10^8$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін барлық жүрістерде Шайқас досына келтіруге болатын ең үлкен жалпы зақымды білдіретін бір бүтін саннан тұратын бір жолды шығарыңыз.

Мысал

Кіріс 1

4
5
1 1 0 3 7
3
0 3 2
9
9 9 8 2 4 4 3 5 3
13
1 1 4 5 1 4 1 9 1 9 8 1 0

Шығыс 1

33
11
750
725