책장 제작

\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