빚

민균이의 별명은 빚쟁이다. 김우현 연구소에서 빌린 돈을 잘 갚지 않는다고 해서 붙은 이름이다.

민균이는 지금까지 $N$번 돈을 빌렸고, $i$번째로 빌린 금액은 $A_i$다. 김우현 연구소는 돈을 돌려받는 방식이 독특하다.

연구소가 빚을 $M$번 갚으라고 명령하면, 민균이는 $N$번의 빚 중에서 $M$번을 마음대로 고른다. 고른 금액을 $B_1, B_2, \dots, B_M$이라고 하면 민균이가 내야 하는 금액은 $\max(B_1, B_2, \dots, B_M) \times M$이다. 여기서 실제로 빌린 금액의 합을 뺀 나머지를 추가 상환액이라고 하자. 즉 추가 상환액은 $\max(B_1, B_2, \dots, B_M) \times M - (B_1 + B_2 + \dots + B_M)$이다.

예를 들어 민균이가 세 번에 걸쳐 $2$, $5$, $3$을 빌렸고 연구소가 빚을 두 번 갚으라고 명령했다고 하자. 첫 번째와 두 번째를 고르면 내야 하는 금액은 $5 \times 2 = 10$이고 추가 상환액은 $10 - (2 + 5) = 3$이다. 첫 번째와 세 번째를 고르면 내야 하는 금액은 $3 \times 2 = 6$이고 추가 상환액은 $6 - (2 + 3) = 1$이다.

민균이는 추가 상환액을 최대한 줄이고 싶다. 연구소가 빚을 $M$번 갚으라고 명령했을 때 나올 수 있는 추가 상환액의 최솟값을 $S(M)$이라고 하자.

$N = 5$이고 빌린 금액이 차례대로 $1, 5, 4, 3, 8$이면 다음과 같다.

• $S(1) = 0$. 무엇을 골라도 추가로 낼 돈이 없다.
• $S(2) = 1$. $5$와 $4$를 고르거나 $4$와 $3$을 고른다.
• $S(3) = 3$. $5, 4, 3$을 고른다.
• $S(4) = 7$. $5, 4, 3, 1$을 고른다.
• $S(5) = 19$. 다섯 번을 모두 고른다.

$N$과 $A_1, A_2, \dots, A_N$이 주어지면 $S(1) + S(2) + \dots + S(N)$을 구하라.

첫 줄에 테스트케이스의 수 $T$ ($1 \le T \le 10$)가 주어진다.

이어지는 $T$개의 줄에는 각각 민균이가 돈을 빌린 횟수 $N$ ($1 \le N \le 4000$)과 빌린 금액 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10000$)이 공백으로 구분되어 순서대로 주어진다.

각 테스트케이스마다 $S(1) + S(2) + \dots + S(N)$을 한 줄에 출력한다.

중간 계산값과 답이 32비트 정수 범위를 넘을 수 있으므로 64비트 정수를 써야 한다.