히스토그램에서 가장 큰 직사각형 리턴즈

길이 $N$의 두 양의 정수 수열 $A$, $B$가 주어진다. $B$의 원소를 임의로 재배열하여 얻은 수열을 $B'$라 하고, $C_i=A_i+B'_i$로 정의한다.

너비가 $1$이고 높이가 $C_1,C_2,\cdots,C_N$인 막대들을 순서대로 놓아 히스토그램을 만든다. $B$를 재배열하는 모든 방법을 고려했을 때, 만들어진 히스토그램에서 구할 수 있는 가장 큰 축에 평행한 직사각형 넓이의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 가능한 넓이의 최댓값을 출력한다.

• $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$)
• 모든 테스트 케이스에 대한 $N^2$의 합은 $2\,250\,000$ 이하이다.