דג ציאן הקטן משחק ב-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