시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 22 7 7 35.000%

문제

상진이는 n개의 책을 담기 위한 책장을 만들려 한다. 그런데 상진이는 외관적인 문제 때문에 반드시 책장을 세개의 칸으로 구분하려 한다. 그런데 책장을 제작하는데는 많은 돈이 들기 때문에 책장의 크기를 최소화 하려 한다.

그런데 책장은 반드시 직사각형의 모양으로 이루어 져야 한다. 그렇다고 하였을 때, 책장의 크기는 다음과 같이 구할 수 있을 것이다. i번째 책의 높이와 두께를 각각 hi와 ti라고 하고, 첫번째 책장에 들어가는 책의 집합을 S1, 두번째 책장을 S2, 세번째 책장을 S3 라고 하였을 때, 책장의 크기는 다음과 같은 식으로 구할 수 있다.

\[(\sum _{ j=1 }^{ 3 }{ max_{i\in S_{j} } h_{i} } )\times( max_{ j=1 }^{ 3 }{ \sum_{i\in S_{j} } t_{i} } )\]

이 식은 직관적으로 쉽게 알 수 있다. 각 칸의 높이는 그 칸에 들어있는 책들의 높이 중 가장 큰 높이가 될 것이고, 책장의 전체 넓이는 각 칸의 너비들 중 가장 큰 너비가 될 것이다. 그런데 각 칸의 너비는 최소한 그 칸에 들어있는 책들의 너비의 합이 되어야 하므로 위와 같은 식이 나오게 된다.

입력

첫째 줄에 책들의 개수 n(1<=n<=70)이 주어진다. 그리고 두번째 줄부터 n+1번째 줄까지 책들의 높이와 두께 hi,ti가 공백을 사이에 두고 주어진다. (단 150<=hi<=300, 5<=ti<=30) 

출력

첫째 줄에 책장의 최소 너비를 출력한다.

예제 입력

4
220 29
195 20
200 9
180 30

예제 출력

18000

힌트