26F. Carpet Exhibition

3000 pts3s256 MB

You are given $n$ carpets, numbered from $1$ to $n$ . Carpet $i$ has length $a_i$ .

You want to lay all the carpets along a straight corridor of the same width as the carpets. You may choose their positions and the order in which you lay them. Wherever carpets overlap, only the one laid last is visible from above.

Every carpet must lie entirely inside the corridor, without being cut or folded. Both endpoints of every carpet must be at integer distances from the left end of the corridor.

The carpets must cover the entire corridor. Viewed from above, the corridor must consist of exactly $n$ consecutive sections, each of length at least $1$ . In the $i$ -th section from the left, only carpet $i$ must be visible.

Find the minimum possible length of the corridor.

Constraints

$1 \le t \le 5000$
$1 \le n \le 5000$
$1 \le a_i \le 10^9$
$\sum n^2 \le 25\ 000\ 000$ over all test cases.

Input

$t$

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

3
3 6 3

Case 2

3
3 3 6

Explanation

Case 1

The first arrangement can expose carpets $1$ , $2$ , and $3$ on segments of lengths $1$ , $3$ , and $3$ , respectively. No corridor shorter than $7$ can accommodate this top view.

Case 2

A corridor of length $6$ is sufficient for the second sequence, and it is impossible to use a shorter corridor because carpet $3$ itself has length $6$ .

Output

Case 1

Case 2

Input

Case 1

3
8 10 3

Case 2

4
4 3 3 4

Case 3

1
7

Explanation

Case 1

A corridor of length $11$ can display the three carpets in the required order. In particular, placing the longest carpet at the bottom is not necessary.

Case 2

The four carpets can be arranged so that the required top view has total length $6$ ; any shorter corridor cannot contain either carpet of length $4$ together with the required visible parts.

Case 3

With only one carpet, the whole corridor must be covered by that carpet.

Output

Case 1

Case 2

Case 3

You are given $n$ carpets, numbered from $1$ to $n$ . Carpet $i$ has length $a_i$ .

Every carpet must lie entirely inside the corridor, without being cut or folded. Both endpoints of every carpet must be at integer distances from the left end of the corridor.

Find the minimum possible length of the corridor.

$1 \le t \le 5000$
$1 \le n \le 5000$
$1 \le a_i \le 10^9$
$\sum n^2 \le 25\ 000\ 000$ over all test cases.

$t$

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

The first arrangement can expose carpets $1$ , $2$ , and $3$ on segments of lengths $1$ , $3$ , and $3$ , respectively. No corridor shorter than $7$ can accommodate this top view.

A corridor of length $6$ is sufficient for the second sequence, and it is impossible to use a shorter corridor because carpet $3$ itself has length $6$ .

A corridor of length $11$ can display the three carpets in the required order. In particular, placing the longest carpet at the bottom is not necessary.

The four carpets can be arranged so that the required top view has total length $6$ ; any shorter corridor cannot contain either carpet of length $4$ together with the required visible parts.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

26F. Carpet Exhibition

Constraints

Input

Output

Samples

26F. Carpet Exhibition

Constraints

Input

Output

Samples