시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 29 10 8 36.364%

문제

상진이는 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) 

출력

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

예제 입력 1

4
220 29
195 20
200 9
180 30

예제 출력 1

18000
W3sicHJvYmxlbV9pZCI6IjIwMDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjNDVcdWM3YTVcdWM4MWNcdWM3OTEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YzljNFx1Yzc3NFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1Y2M0NVx1Yzc0NCBcdWIyZjRcdWFlMzAgXHVjNzA0XHVkNTVjIFx1Y2M0NVx1YzdhNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjMGMxXHVjOWM0XHVjNzc0XHViMjk0IFx1YzY3OFx1YWQwMFx1YzgwMVx1Yzc3OCBcdWJiMzhcdWM4MWMgXHViNTRjXHViYjM4XHVjNWQwIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWNjNDVcdWM3YTVcdWM3NDQgXHVjMTM4XHVhYzFjXHVjNzU4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVjYzQ1XHVjN2E1XHVjNzQ0IFx1YzgxY1x1Yzc5MVx1ZDU1OFx1YjI5NFx1YjM3MFx1YjI5NCBcdWI5Y2VcdWM3NDAgXHViM2M4XHVjNzc0IFx1YjRlNFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjYzQ1XHVjN2E1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwXHViMzcwIFx1Y2M0NVx1YzdhNVx1Yzc0MCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjQgXHVjODM4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViODA3XHViMmU0XHVhY2UwIFx1ZDU1OFx1YzYwMFx1Yzc0NCBcdWI1NGMsIFx1Y2M0NVx1YzdhNVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjYzQ1XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWI0NTBcdWFlZDhcdWI5N2MgXHVhYzAxXHVhYzAxIGhpXHVjNjQwIHRpXHViNzdjXHVhY2UwIFx1ZDU1OFx1YWNlMCwgXHVjY2FiXHViYzg4XHVjOWY4IFx1Y2M0NVx1YzdhNVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWIyOTQgXHVjYzQ1XHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0NCBTPHN1Yj4xPFwvc3ViPiwgXHViNDUwXHViYzg4XHVjOWY4IFx1Y2M0NVx1YzdhNVx1Yzc0NCBTPHN1Yj4yPFwvc3ViPiwgXHVjMTM4XHViYzg4XHVjOWY4IFx1Y2M0NVx1YzdhNVx1Yzc0NCZuYnNwO1M8c3ViPjM8XC9zdWI+IFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM2MDBcdWM3NDQgXHViNTRjLCBcdWNjNDVcdWM3YTVcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzNjXHViODVjIFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cXFsoXFxzdW0gX3sgaj0xIH1eeyAzIH17Jm5ic3A7bWF4X3tpXFxpbiBTX3tqfSB9IGhfe2l9IH0gKVxcdGltZXMoIG1heF97IGo9MSB9XnsgMyB9eyBcXHN1bV97aVxcaW4gU197an0gfSB0X3tpfSB9IClcXF08XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YzJkZFx1Yzc0MCBcdWM5YzFcdWFkMDBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMjdkXHVhYzhjIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWFkZjggXHVjZTc4XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWNjNDVcdWI0ZTRcdWM3NTggXHViMTkyXHVjNzc0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWI0MjAgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWNjNDVcdWM3YTVcdWM3NTggXHVjODA0XHVjY2I0IFx1YjExM1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjEwOFx1YmU0NFx1YjRlNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWIxMDhcdWJlNDRcdWFjMDAgXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTA4XHViZTQ0XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWFkZjggXHVjZTc4XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWNjNDVcdWI0ZTRcdWM3NTggXHViMTA4XHViZTQ0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTU4XHViYmMwXHViODVjIFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzc0IFx1YjA5OFx1YzYyNFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2M0NVx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMTggbigxJmx0Oz1uJmx0Oz03MClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBuKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1Y2M0NVx1YjRlNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWM2NDAgXHViNDUwXHVhZWQ4IGg8c3ViPmk8XC9zdWI+LHQ8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFx1YjJlOCAxNTAmbHQ7PWg8c3ViPmk8XC9zdWI+Jmx0Oz0zMDAsIDUmbHQ7PXQ8c3ViPmk8XC9zdWI+Jmx0Oz0zMCkmbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2M0NVx1YzdhNVx1Yzc1OCBcdWNkNWNcdWMxOGMgXHViMTA4XHViZTQ0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMDAwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEJvb2tjYXNlIiwiZGVzY3JpcHRpb24iOiI8cD5ObyB3b25kZXIgdGhlIG9sZCBib29rY2FzZSBjYXZlZCB1bmRlciB0aGUgbWFzc2l2ZSBwaWxlcyBvZiBib29rcyBUb20gaGFkIHN0YWNrZWQgb24gaXQuIEhlIGhhZCBiZXR0ZXIgYnVpbGQgYSBuZXcgb25lLCB0aGlzIHRpbWUgbGFyZ2UgZW5vdWdoIHRvIGhvbGQgYWxsIG9mIGhpcyBib29rcy4gVG9tIGZpbmRzIGl0IHByYWN0aWNhbCB0byBoYXZlIHRoZSBib29rcyBjbG9zZSBhdCBoYW5kIHdoZW4gaGUgd29ya3MgYXQgaGlzIGRlc2suIFRoZXJlZm9yZSwgaGUgaXMgaW1hZ2luaW5nIGEgY29tcGFjdCBzb2x1dGlvbiB3aXRoIHRoZSBib29rY2FzZSBzdGFuZGluZyBvbiB0aGUgYmFjayBvZiB0aGUgZGVzay4gT2J2aW91c2x5LCB0aGlzIHdvdWxkIHB1dCBzb21lIHJlc3RyaWN0aW9ucyBvbiB0aGUgc2l6ZSBvZiB0aGUgYm9va2Nhc2UsIGl0IHNob3VsZCBwcmVmZXJhYmx5IGJlIGFzIHNtYWxsIGFzIHBvc3NpYmxlLiBJbiBhZGRpdGlvbiwgVG9tIHdvdWxkIGxpa2UgdGhlIGJvb2tjYXNlIHRvIGhhdmUgZXhhY3RseSB0aHJlZSBzaGVsdmVzIGZvciBhZXN0aGV0aWNhbCByZWFzb25zLjxcL3A+XHJcblxyXG48cD5Xb25kZXJpbmcgaG93IHNtYWxsIGhpcyBib29rY2FzZSBjb3VsZCBiZSwgaGUgbW9kZWxzIHRoZSBwcm9ibGVtIGFzIGZvbGxvd3MuIEhlIG1lYXN1cmVzIHRoZSBoZWlnaHQgaGkgYW5kIHRoaWNrbmVzcyB0aSBvZiBlYWNoIGJvb2sgaSBhbmQgaGUgc2Vla3MgYSBwYXJ0aXRpb24gb2YgdGhlIGJvb2tzIGluIHRocmVlIG5vbi1lbXB0eSBzZXRzIFM8c3ViPjE8XC9zdWI+LFM8c3ViPjI8XC9zdWI+LFM8c3ViPjM8XC9zdWI+IHN1Y2ggdGhhdCBcXCgoXFxzdW0gX3sgaj0xIH1eeyAzIH17Jm5ic3A7bWF4X3tpXFxpbiBTX3tqfSB9IGhfe2l9IH0gKVxcdGltZXMoIG1heF97IGo9MSB9XnsgMyB9eyBcXHN1bV97aVxcaW4gU197an0gfSB0X3tpfSB9IClcXCkmbmJzcDtpcyBtaW5pbWl6ZWQsIGkuZS4gdGhlIGFyZWEgb2YgdGhlIGJvb2tjYXNlIGFzIHNlZW4gd2hlbiBzdGFuZGluZyBpbiBmcm9udCBvZiBpdCAodGhlIGRlcHRoIG5lZWRlZCBpcyBvYnZpb3VzbHkgdGhlIGxhcmdlc3Qgd2lkdGggb2YgYWxsIGhpcyBib29rcywgcmVnYXJkbGVzcyBvZiB0aGUgcGFydGl0aW9uKS4gTm90ZSB0aGF0IHRoaXMgZm9ybXVsYSBkb2VzIG5vdCBnaXZlIHRoZSBleGFjdCBhcmVhIG9mIHRoZSBib29rY2FzZSwgc2luY2UgdGhlIGFjdHVhbCBzaGVsdmVzIGNhdXNlIGEgc21hbGwgYWRkaXRpb25hbCBoZWlnaHQsIGFuZCB0aGUgc2lkZXMgY2F1c2UgYSBzbWFsbCBhZGRpdGlvbmFsIHdpZHRoLiBGb3Igc2ltcGxpY2l0eSwgd2Ugd2lsbCBpZ25vcmUgdGhpcyBzbWFsbCBkaXNjcmVwYW5jeS48XC9wPlxyXG5cclxuPHA+VGhpbmtpbmcgYSBtb21lbnQgb24gdGhlIHByb2JsZW0sIFRvbSByZWFsaXplcyBoZSB3aWxsIG5lZWQgYSBjb21wdXRlciBwcm9ncmFtIHRvIGRvIHRoZSBqb2IuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgYmVnaW5zIHdpdGggYSBwb3NpdGl2ZSBudW1iZXIgb24gYSBsaW5lIG9mIGl0cyBvd24gdGVsbGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgKGF0IG1vc3QgMjApLiBGb3IgZWFjaCB0ZXN0IGNhc2UgdGhlcmUgaXMgb25lIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIE4sIDMgJmxlOyBOICZsZTsgNzAgZ2l2aW5nIHRoZSBudW1iZXIgb2YgYm9va3MuIFRoZW4gTiBsaW5lcyBmb2xsb3cgZWFjaCBjb250YWluaW5nIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBoPHN1Yj5pPFwvc3ViPiwgdDxzdWI+aTxcL3N1Yj4sIHNhdGlzZnlpbmcgMTUwICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyAzMDAgYW5kIDUgJmxlOyB0PHN1Yj5pPFwvc3ViPiAmbGU7IDMwLCB0aGUgaGVpZ2h0IGFuZCB0aGlja25lc3Mgb2YgYm9vayBpIHJlc3BlY3RpdmVseSwgaW4gbWlsbGltZXRlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbWluaW11bSBhcmVhIChoZWlnaHQgdGltZXMgd2lkdGgpIG9mIGEgdGhyZWUtc2hlbGYgYm9va2Nhc2UgY2FwYWJsZSBvZiBob2xkaW5nIGFsbCB0aGUgYm9va3MsIGV4cHJlc3NlZCBpbiBzcXVhcmUgbWlsbGltZXRlcnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d