小青魚緊係度玩《殺戮尖塔 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