小青魚正在玩《殺戮尖塔 II》（Slay the Spire II），並選擇了角色「靜默獵手」（Silent）。
小青魚現在需要與一個戰鬥夥伴（Battle Friend）進行戰鬥。初始時，戰鬥夥伴的「中毒」（Poison）層數和你的「加速劑」（Accelerant）等級均為 $0$。在接下來的 $n$ 回合中，每回合將依次發生以下事件：
使用「致命毒藥」（Deadly Poison）：將戰鬥夥伴的中毒層數增加 $x_i$。
選擇是否使用「加速劑」：選擇是否將你的加速劑等級增加 $1$。
觸發中毒效果：設你的加速劑等級為 $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