책장 제작

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

요약

책 n권을 세 개의 선반에 나눠 담아 높이 합과 최대 두께 합의 곱으로 정의되는 책장 면적을 최소화하는 문제입니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 정렬, 완전 탐색
정답자: 아직 제출이 없습니다

문제

\uC0C1\uC9C4\uC774\uB294 n\uAD8C\uC758 \uCC45\uC744 \uB123\uC744 \uCC45\uC7A5\uC744 \uB9CC\uB4E4\uB824\uACE0 \uD55C\uB2E4. \uCC45\uC7A5\uC740 \uC678\uAD00 \uB54C\uBB38\uC5D0 \uBC18\uB4DC\uC2DC \uC138 \uCE78\uC73C\uB85C \uB098\uB258\uBA70, \uAC01 \uCC45\uC740 \uC138 \uCE78 \uC911 \uC815\uD655\uD788 \uD55C \uCE78\uC5D0 \uB193\uC544\uC57C \uD55C\uB2E4. \uAC01 \uCE78\uC5D0\uB294 \uC801\uC5B4\uB3C4 \uD55C \uAD8C\uC758 \uCC45\uC774 \uB4E4\uC5B4\uAC04\uB2E4.

i\uBC88\uC9F8 \uCC45\uC758 \uB192\uC774\uB97C h_i, \uB450\uAED8\uB97C t_i\uB77C\uACE0 \uD558\uC790. \uC138 \uCE78\uC5D0 \uB4E4\uC5B4\uAC00\uB294 \uCC45\uC758 \uC9D1\uD569\uC744 \uAC01\uAC01 S_1, S_2, S_3\uC774\uB77C\uACE0 \uD558\uBA74 \uCC45\uC7A5\uC758 \uBA74\uC801\uC740 \uB2E4\uC74C\uACFC \uAC19\uB2E4.

[ \left(\sum_{j=1}^{3} \max_{i \in S_j} h_i\right) \times \left(\max_{1 \le j \le 3} \sum_{i \in S_j} t_i\right) ]

\uAC01 \uCE78\uC758 \uB192\uC774\uB294 \uADF8 \uCE78\uC5D0 \uB4E4\uC5B4\uAC04 \uCC45\uB4E4\uC758 \uB192\uC774 \uC911 \uCD5C\uB313\uAC12\uC774\uACE0, \uCC45\uC7A5\uC758 \uC804\uCCB4 \uB108\uBE44\uB294 \uC138 \uCE78\uC758 \uB450\uAED8 \uD569 \uC911 \uCD5C\uB313\uAC12\uC774\uB2E4. \uBAA8\uB4E0 \uCC45\uC744 \uC138 \uCE78\uC5D0 \uB098\uB204\uC5B4 \uB123\uC744 \uB54C \uAC00\uB2A5\uD55C \uCC45\uC7A5 \uBA74\uC801\uC758 \uCD5C\uC19F\uAC12\uC744 \uAD6C\uD558\uB77C.

입력

첫째 줄에 책의 수 n이 주어진다. 다음 n개 줄에는 각 책의 높이 h_i와 두께 t_i가 공백으로 구분되어 주어진다.

출력

가능한 책장 면적의 최솟값을 출력한다.

제한

3 ≤ n ≤ 70
150 ≤ h_i ≤ 300
5 ≤ t_i ≤ 30

예제2

예제 1
입력
```
4
220 29
195 20
200 9
180 30
```
예상 출력
```
18000
```

예제 2

입력

예상 출력