집중력 카드

시간 제한1초메모리 제한128 MB

요약

각각 90도 회전할 수 있는 W×H 카드 N장으로 빈틈없이 채운 직사각형을 만들고, 그 둘레의 최솟값을 구한다.

난이도: 어려움10점 중 8점
유형: 수학, 기하, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

스탠(Stan)은 $N$ 장으로 이루어진 집중력 카드 한 벌을 가지고 있습니다. 그는 이 카드들을 서로 맞닿게 이어 붙여 빈틈 없이 채워진 하나의 직사각형을 만들되, 그 직사각형의 둘레를 최소로 하려고 합니다. 각 카드는 가로 $W$ mm, 세로 $H$ mm인 직사각형입니다.

각 카드는 $90^\circ$ 회전하여 놓을 수 있으며, 카드들이 서로 겹치거나 빈틈을 남기지 않고 직사각형을 정확히 덮기만 한다면 어떤 방식으로 배열해도 됩니다(반드시 격자 모양일 필요는 없습니다).

그림 1: 집중력 카드

입력

입력의 첫째 줄에는 테스트 케이스의 수 $C$ 가 주어집니다. 이어지는 각 줄에는 한 테스트 케이스에 해당하는 $N$ , $W$ , $H$ 가 주어지며, 세 값은 모두 $1000$ 이하의 양의 정수입니다.

출력

각 테스트 케이스마다, 만들 수 있는 직사각형의 최소 둘레를 한 줄에 하나씩 출력합니다.

예제3

예제 1

입력

예상 출력

2600
2800
3800

예제 2
입력
```
1
1 1 1
```
예상 출력
```
4
```
예제 3
입력
```
1
6 5 5
```
예상 출력
```
50
```