ปลาเขียวตัวน้อยกำลังเล่นเกม 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