TopCoder

Thumb output jddoia
$\huge 南ことり$
$https://www.ototot.com.tw/TIOJ/ \\我要拿牌、去東京、變紅色,那就努力吧 \\ 確かな今よりも新しい夢つかまえたい$

User's AC Ratio

100.0% (10/10)

Submission's AC Ratio

78.6% (11/14)

Tags

Description

經過了一個似乎平安的晚上...
「喔膩醬...」你身邊的祈說道
「我還不知道喔膩醬叫什麼名字耶」
「啊...我叫小志(jizzin)」
「恩!還有跟喔膩醬說喔,我的姓是「天」喔,不過喔膩醬直接叫我名字就好」
祈繼續說到,
「那個,感謝喔膩醬救了我一命,我決定給喔膩醬一個特別的獎勵喔」
「喔喔喔!這個蘿莉果然沒有白撿回來!我的內心,內心的某個深處絕醒了啊啊啊啊!!」你暗爽著。
「那你到底要給我什麼獎勵呢?」你心中早已幻想過數種情況。
「呵呵,那就要看我有多喜歡喔膩醬囉。」
「為了男人的尊嚴,我...我一定要攻略下這隻小蘿莉。」
因此你決定利用這段時間好好增加對祈的好感度
你想到了有N種事情可以做(如:跟她說故事、餵她吃棒棒糖或是一起做體操等等),第i種事情可以增加好感度a_i 。

當然,做太多事也是會累的,因此當你第i種事情放在第j個來做時,你實際上對祈的好感度只會增加a_i −j。
你要選那些事情來做並要如何決定順序,才能增加最多好感度呢?

Input Format

第一行有一個正整數T,代表有T筆測資。
每個測資的第一行有一個正整數N代表有多少種事情可以做,第二行有N個正整數,第i個數代表a_i ,即做第i件事情的好感度。

Output Format

對於每筆測資輸出一行,包含一個數字,代表好感度增加的最大值。

Sample Input

3
5
1 2 3 4 5
5
1 1 1 1 1
5
1 4 2 7 5

Sample Output

6
0
10

Hints

對於範例測資的第一筆輸入,你可以先做第4件事,獲得4−1=3的好感度,再做第5件事,獲得5−2=3的好感度,而得到最大值6。
第二筆輸入,你乾脆不要做任何事。
第三筆輸入你可以依序作第2,5,4件事。

對於所有測試資料 : ai≤104
測資組A : T≤20,N≤10
測資組B : T≤20,N≤50
測資組C : T≤20,N≤3000
測資組D : T≤20,N≤105

Problem Source

Step5

Subtasks

For Testdata: 0 ~ 1, Score: 20
For Testdata: 2 ~ 3, Score: 20
For Testdata: 4 ~ 7, Score: 45
For Testdata: 8 ~ 9, Score: 15
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536