시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhZGY4XHViN2YwXHViMzcwIFx1Y2M0NVx1YzdhNVx1Yzc0MCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YmFhOFx1YzU5MVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjQgXHVjODM4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViODA3XHViMmU0XHVhY2UwIFx1ZDU1OFx1YzYwMFx1Yzc0NCBcdWI1NGMsIFx1Y2M0NVx1YzdhNVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjYzQ1XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MCBcdWI0NTBcdWFlZDhcdWI5N2MgXHVhYzAxXHVhYzAxIGhpXHVjNjQwIHRpXHViNzdjXHVhY2UwIFx1ZDU1OFx1YWNlMCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWNjNDVcdWM3YTVcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViMjk0IFx1Y2M0NVx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NDQgUzxzdWI+MTxcL3N1Yj4sIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjYzQ1XHVjN2E1XHVjNzQ0IFM8c3ViPjI8XC9zdWI+LCBcdWMxMzggXHViYzg4XHVjOWY4IFx1Y2M0NVx1YzdhNVx1Yzc0NCZuYnNwO1M8c3ViPjM8XC9zdWI+IFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM2MDBcdWM3NDQgXHViNTRjLCBcdWNjNDVcdWM3YTVcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzNjXHViODVjIFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cXFsoXFxzdW0gX3sgaj0xIH1eeyAzIH17Jm5ic3A7bWF4X3tpXFxpbiBTX3tqfSB9IGhfe2l9IH0gKVxcdGltZXMoIG1heF97IGo9MSB9XnsgMyB9eyBcXHN1bV97aVxcaW4gU197an0gfSB0X3tpfSB9IClcXF08XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YzJkZFx1Yzc0MCBcdWM5YzFcdWFkMDBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjMjdkXHVhYzhjIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCBcdWFkZjggXHVjZTc4XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWNjNDVcdWI0ZTRcdWM3NTggXHViMTkyXHVjNzc0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWI0MjAgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWNjNDVcdWM3YTVcdWM3NTggXHVjODA0XHVjY2I0IFx1YjExM1x1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjZTc4XHVjNzU4IFx1YjEwOFx1YmU0NFx1YjRlNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWIxMDhcdWJlNDRcdWFjMDAgXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1YWMwMSBcdWNlNzhcdWM3NTggXHViMTA4XHViZTQ0XHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWFkZjggXHVjZTc4XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWNjNDVcdWI0ZTRcdWM3NTggXHViMTA4XHViZTQ0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTU4XHViYmMwXHViODVjIFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzc0IFx1YjA5OFx1YzYyNFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2M0NVx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMTggbigxJmx0Oz1uJmx0Oz03MClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgbisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWNjNDVcdWI0ZTRcdWM3NTggXHViMTkyXHVjNzc0XHVjNjQwIFx1YjQ1MFx1YWVkOCBoPHN1Yj5pPFwvc3ViPix0PHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChcdWIyZTggMTUwJmx0Oz1oPHN1Yj5pPFwvc3ViPiZsdDs9MzAwLCA1Jmx0Oz10PHN1Yj5pPFwvc3ViPiZsdDs9MzApJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjNDVcdWM3YTVcdWM3NTggXHVjZDVjXHVjMThjIFx1YjEwOFx1YmU0NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAwMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBCb29rY2FzZSIsImRlc2NyaXB0aW9uIjoiPHA+Tm8gd29uZGVyIHRoZSBvbGQgYm9va2Nhc2UgY2F2ZWQgdW5kZXIgdGhlIG1hc3NpdmUgcGlsZXMgb2YgYm9va3MgVG9tIGhhZCBzdGFja2VkIG9uIGl0LiBIZSBoYWQgYmV0dGVyIGJ1aWxkIGEgbmV3IG9uZSwgdGhpcyB0aW1lIGxhcmdlIGVub3VnaCB0byBob2xkIGFsbCBvZiBoaXMgYm9va3MuIFRvbSBmaW5kcyBpdCBwcmFjdGljYWwgdG8gaGF2ZSB0aGUgYm9va3MgY2xvc2UgYXQgaGFuZCB3aGVuIGhlIHdvcmtzIGF0IGhpcyBkZXNrLiBUaGVyZWZvcmUsIGhlIGlzIGltYWdpbmluZyBhIGNvbXBhY3Qgc29sdXRpb24gd2l0aCB0aGUgYm9va2Nhc2Ugc3RhbmRpbmcgb24gdGhlIGJhY2sgb2YgdGhlIGRlc2suIE9idmlvdXNseSwgdGhpcyB3b3VsZCBwdXQgc29tZSByZXN0cmljdGlvbnMgb24gdGhlIHNpemUgb2YgdGhlIGJvb2tjYXNlLCBpdCBzaG91bGQgcHJlZmVyYWJseSBiZSBhcyBzbWFsbCBhcyBwb3NzaWJsZS4gSW4gYWRkaXRpb24sIFRvbSB3b3VsZCBsaWtlIHRoZSBib29rY2FzZSB0byBoYXZlIGV4YWN0bHkgdGhyZWUgc2hlbHZlcyBmb3IgYWVzdGhldGljYWwgcmVhc29ucy48XC9wPlxyXG5cclxuPHA+V29uZGVyaW5nIGhvdyBzbWFsbCBoaXMgYm9va2Nhc2UgY291bGQgYmUsIGhlIG1vZGVscyB0aGUgcHJvYmxlbSBhcyBmb2xsb3dzLiBIZSBtZWFzdXJlcyB0aGUgaGVpZ2h0IGhpIGFuZCB0aGlja25lc3MgdGkgb2YgZWFjaCBib29rIGkgYW5kIGhlIHNlZWtzIGEgcGFydGl0aW9uIG9mIHRoZSBib29rcyBpbiB0aHJlZSBub24tZW1wdHkgc2V0cyBTPHN1Yj4xPFwvc3ViPixTPHN1Yj4yPFwvc3ViPixTPHN1Yj4zPFwvc3ViPiBzdWNoIHRoYXQgXFwoKFxcc3VtIF97IGo9MSB9XnsgMyB9eyZuYnNwO21heF97aVxcaW4gU197an0gfSBoX3tpfSB9IClcXHRpbWVzKCBtYXhfeyBqPTEgfV57IDMgfXsgXFxzdW1fe2lcXGluIFNfe2p9IH0gdF97aX0gfSApXFwpJm5ic3A7aXMgbWluaW1pemVkLCBpLmUuIHRoZSBhcmVhIG9mIHRoZSBib29rY2FzZSBhcyBzZWVuIHdoZW4gc3RhbmRpbmcgaW4gZnJvbnQgb2YgaXQgKHRoZSBkZXB0aCBuZWVkZWQgaXMgb2J2aW91c2x5IHRoZSBsYXJnZXN0IHdpZHRoIG9mIGFsbCBoaXMgYm9va3MsIHJlZ2FyZGxlc3Mgb2YgdGhlIHBhcnRpdGlvbikuIE5vdGUgdGhhdCB0aGlzIGZvcm11bGEgZG9lcyBub3QgZ2l2ZSB0aGUgZXhhY3QgYXJlYSBvZiB0aGUgYm9va2Nhc2UsIHNpbmNlIHRoZSBhY3R1YWwgc2hlbHZlcyBjYXVzZSBhIHNtYWxsIGFkZGl0aW9uYWwgaGVpZ2h0LCBhbmQgdGhlIHNpZGVzIGNhdXNlIGEgc21hbGwgYWRkaXRpb25hbCB3aWR0aC4gRm9yIHNpbXBsaWNpdHksIHdlIHdpbGwgaWdub3JlIHRoaXMgc21hbGwgZGlzY3JlcGFuY3kuPFwvcD5cclxuXHJcbjxwPlRoaW5raW5nIGEgbW9tZW50IG9uIHRoZSBwcm9ibGVtLCBUb20gcmVhbGl6ZXMgaGUgd2lsbCBuZWVkIGEgY29tcHV0ZXIgcHJvZ3JhbSB0byBkbyB0aGUgam9iLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGJlZ2lucyB3aXRoIGEgcG9zaXRpdmUgbnVtYmVyIG9uIGEgbGluZSBvZiBpdHMgb3duIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIChhdCBtb3N0IDIwKS4gRm9yIGVhY2ggdGVzdCBjYXNlIHRoZXJlIGlzIG9uZSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBOLCAzICZsZTsgTiAmbGU7IDcwIGdpdmluZyB0aGUgbnVtYmVyIG9mIGJvb2tzLiBUaGVuIE4gbGluZXMgZm9sbG93IGVhY2ggY29udGFpbmluZyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgaDxzdWI+aTxcL3N1Yj4sIHQ8c3ViPmk8XC9zdWI+LCBzYXRpc2Z5aW5nIDE1MCAmbGU7IGg8c3ViPmk8XC9zdWI+ICZsZTsgMzAwIGFuZCA1ICZsZTsgdDxzdWI+aTxcL3N1Yj4gJmxlOyAzMCwgdGhlIGhlaWdodCBhbmQgdGhpY2tuZXNzIG9mIGJvb2sgaSByZXNwZWN0aXZlbHksIGluIG1pbGxpbWV0ZXJzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gYXJlYSAoaGVpZ2h0IHRpbWVzIHdpZHRoKSBvZiBhIHRocmVlLXNoZWxmIGJvb2tjYXNlIGNhcGFibGUgb2YgaG9sZGluZyBhbGwgdGhlIGJvb2tzLCBleHByZXNzZWQgaW4gc3F1YXJlIG1pbGxpbWV0ZXJzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==