#220 Largest Rectangle in a Histogram Returns

Statement

Statement language

Two positive integer sequences $A$ and $B$ of length $N$ are given. Let $B'$ be any permutation of $B$ , and define $C_i=A_i+B'_i$ .

Build a histogram from unit-width bars of heights $C_1,C_2,\cdots,C_N$ in order. Over every possible permutation of , find the maximum possible area of the largest axis-aligned rectangle in the resulting histogram.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the maximum possible area.

Constraints

$1 \leq T \leq 1\,000$
$1 \leq N \leq 1\,500$
$1 \leq A_{}$ ()

Subtasks

#	Score	Constraints
1	30	$N \leq 80$ , and the sum of $N^2$ over all test cases does not exceed $10\,000$ .
2	70	No additional constraints.

Samples

Input

Output

12

With $B'=(3,2,1)$ , every bar has height $4$ , giving a rectangle of area $12$ .