#220 Largest Rectangle in a Histogram Returns

Loading problem...

Preparing the statement, recent submissions, and submit form.

Time limit: 7000 ms
Memory limit: 1024 MB
Checker: DIFF
Solve threshold: 100

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 $B$ , 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$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_N$

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_i,B_i \leq 10^9$ ( $1 \leq i \leq N$ )
The sum of $N^2$ over all test cases does not exceed $2\,250\,000$ .

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

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

Editorial

View editorial