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

문제

지문 언어

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

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

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

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

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

#	점수	제한
1	30	$N \leq 80$ 이고, 모든 테스트 케이스에 대한 $N^2$ 의 합은 $10\,000$ 이하이다.
2	70	추가적인 제약이 없다.

입력

출력

12

$B'=(3,2,1)$ 로 두면 모든 막대의 높이가 $4$ 이므로 넓이 $12$ 인 직사각형을 만들 수 있다.