12831283 SUSTech Online Judge
Problem 1283 --Cut The Stick Pro

## 1283: Cut The Stick Pro

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1056  Solved: 218
[Submit][Status][Web Board]

## Description

Lanran wants to cut one stick with length L into exactly N sticks with length $$L_i(i=1,2...N)$$, so $$L = \sum_{i=1}^{N}{L_i}$$. However, the cost to cut one stick into two pieces is the length of the stick, which means cutting a stick with length x will cost x. Now he wants to know the minimal cost if he cuts stick optimally to get N sticks.

## Input

The first line will be an integer $$T (1 \leq T \leq 5)$$, which is the number of test cases.

For each test, the first line contains an integer N $$(1 \leq N \leq 10^5 )$$ — the number of sticks Lanran needs to get. Then the next line contains N  integers, the i-th integer $$L_i (1 \leq p_i \leq 10^5)$$ indicates the length of N sticks Lanran wants to get.

## Output

For each case print the minimal cost if Lanran cuts stick optimally to get N sticks.

## Sample Input

1
4
1 4 2 6

## Sample Output

23

[Submit][Status]