시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 264 78 55 29.891%

문제

농부 상헌이는 선재의 부동산에서 N개의 땅을 모두 사려고 한다. 땅은 Wi * Hi 크기의 직사각형으로 생각할 수 있다.

선재는 그동안 땅 하나의 가격을 Wi * Hi로 매겨서 팔았는데, 사실 요즘 선재는 장사가 잘 안된다. 손님이 급한 선재는 다음과 같은 묶음 할인 행사를 통해서 땅을 팔고 있다.

  • 여러 개의 땅을 살 때는, (해당 땅 중 Wi의 최댓값) * (해당 땅 중 Hi의 최댓값) 으로 가격을 매긴다.

상헌이는 선재의 행사가 매우 좋다고 생각해서 땅을 살 준비를 하고 있었지만, 땅을 어떻게 묶어사는지에 따라 가격이 천차만별이라는 사실을 깨닫게 되었다! 상헌이가 최소 비용으로 땅을 묶어서 살 경우, 최소 비용은 얼마일까?

입력

첫번째 줄에 N이 주어진다. (1 <= N <= 50000)

이후 N개의 줄에 Wi, Hi가 주어진다. (1 <= Wi, Hi <= 1000000)

출력

상헌이가 땅을 사는 최소 비용을 출력하라.

예제 입력 1

4
100 1
15 15
20 5
1 100

예제 출력 1

500

힌트

(1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다.

W3sicHJvYmxlbV9pZCI6IjYxNzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI1NDVcdWI1MzBcdWJhMzlcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjE4ZFx1YmQ4MCBcdWMwYzFcdWQ1Y2NcdWM3NzRcdWIyOTQgXHVjMTIwXHVjN2FjXHVjNzU4IFx1YmQ4MFx1YjNkOVx1YzBiMFx1YzVkMFx1YzExYyBOXHVhYzFjXHVjNzU4IFx1YjU0NVx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjMGFjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViNTQ1XHVjNzQwIFc8c3ViPmk8XC9zdWI+ICogSDxzdWI+aTxcL3N1Yj4gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjN2FjXHViMjk0IFx1YWRmOFx1YjNkOVx1YzU0OCBcdWI1NDUgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0NCBXPHN1Yj5pPFwvc3ViPiAqIEg8c3ViPmk8XC9zdWI+XHViODVjIFx1YjllNFx1YWNhOFx1YzExYyBcdWQzMTRcdWM1NThcdWIyOTRcdWIzNzAsIFx1YzBhY1x1YzJlNCBcdWM2OTRcdWM5OTggXHVjMTIwXHVjN2FjXHViMjk0IFx1YzdhNVx1YzBhY1x1YWMwMCBcdWM3OTggXHVjNTQ4XHViNDFjXHViMmU0LiBcdWMxOTBcdWIyZDhcdWM3NzQgXHVhZTA5XHVkNTVjIFx1YzEyMFx1YzdhY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmIzNlx1Yzc0YyBcdWQ1NjBcdWM3NzggXHVkNTg5XHVjMGFjXHViOTdjIFx1ZDFiNVx1ZDU3NFx1YzExYyBcdWI1NDVcdWM3NDQgXHVkMzE0XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YjU0NVx1Yzc0NCBcdWMwYjQgXHViNTRjXHViMjk0LCAoXHVkNTc0XHViMmY5IFx1YjU0NSBcdWM5MTEgVzxzdWI+aTxcL3N1Yj5cdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyKSAqIChcdWQ1NzRcdWIyZjkgXHViNTQ1IFx1YzkxMSBIPHN1Yj5pPFwvc3ViPlx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTIpIFx1YzczY1x1Yjg1YyBcdWFjMDBcdWFjYTlcdWM3NDQgXHViOWU0XHVhZTM0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzBjMVx1ZDVjY1x1Yzc3NFx1YjI5NCBcdWMxMjBcdWM3YWNcdWM3NTggXHVkNTg5XHVjMGFjXHVhYzAwIFx1YjllNFx1YzZiMCBcdWM4OGJcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTc0XHVjMTFjIFx1YjU0NVx1Yzc0NCBcdWMwYjQgXHVjOTAwXHViZTQ0XHViOTdjIFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM1YzhcdWM5YzBcdWI5Y2MsIFx1YjU0NVx1Yzc0NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHViYjM2XHVjNWI0XHVjMGFjXHViMjk0XHVjOWMwXHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWFjMDBcdWFjYTlcdWM3NzQgXHVjYzljXHVjYzI4XHViOWNjXHViY2M0XHVjNzc0XHViNzdjXHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0NCBcdWFlNjhcdWIyZWJcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0ISBcdWMwYzFcdWQ1Y2NcdWM3NzRcdWFjMDAgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1YzczY1x1Yjg1YyBcdWI1NDVcdWM3NDQgXHViYjM2XHVjNWI0XHVjMTFjIFx1YzBiNCBcdWFjYmRcdWM2YjAsIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDAgXHVjNWJjXHViOWM4XHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmx0Oz0gTiAmbHQ7PSA1MDAwMCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNmM0IE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFc8c3ViPmk8XC9zdWI+LCBIPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IFc8c3ViPmk8XC9zdWI+LCBIPHN1Yj5pPFwvc3ViPiAmbHQ7PSAxMDAwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzBjMVx1ZDVjY1x1Yzc3NFx1YWMwMCBcdWI1NDVcdWM3NDQgXHVjMGFjXHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD4oMSkgXC8gKDQpIFwvICgyLCAzKSBcdWM3M2NcdWI4NWMgXHViNTQ1XHVjNzQ0IFx1YmIzNlx1YzViNCBcdWMwYWNcdWJjZjRcdWM3OTAuIFx1YzBjMVx1ZDVjY1x1Yzc3NFx1YjI5NCAxMDAgKiAxICsgMjAgKiAxNSArIDEgKiAxMDAgPSA1MDBcdWM3NTggXHVhYzAwXHVhY2E5XHVjNWQwIFx1YjU0NVx1Yzc0NCBcdWMwYjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjYxNzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMYW5kIEFjcXVpc2l0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBpcyBjb25zaWRlcmluZyBidXlpbmcgbW9yZSBsYW5kIGZvciB0aGUgZmFybSBhbmQgaGFzIGhpcyBleWUgb24gTiAoMSAmbHQ7PSBOICZsdDs9IDUwLDAwMCkgYWRkaXRpb25hbCByZWN0YW5ndWxhciBwbG90cywgZWFjaCB3aXRoIGludGVnZXIgZGltZW5zaW9ucyAoMSAmbHQ7PSB3aWR0aF9pICZsdDs9IDEsMDAwLDAwMDsgMSAmbHQ7PSBsZW5ndGhfaSAmbHQ7PSAxLDAwMCwwMDApLjxcL3A+XHJcblxyXG48cD5JZiBGSiB3YW50cyB0byBidXkgYSBzaW5nbGUgcGllY2Ugb2YgbGFuZCwgdGhlIGNvc3QgaXMgJDFcL3NxdWFyZSB1bml0LCBidXQgc2F2aW5ncyBhcmUgYXZhaWxhYmxlIGZvciBsYXJnZSBwdXJjaGFzZXMuIEhlIGNhbiBidXkgYW55IG51bWJlciBvZiBwbG90cyBvZiBsYW5kIGZvciBhIHByaWNlIGluIGRvbGxhcnMgdGhhdCBpcyB0aGUgd2lkdGggb2YgdGhlIHdpZGVzdCBwbG90IHRpbWVzIHRoZSBsZW5ndGggb2YgdGhlIGxvbmdlc3QgcGxvdC4gT2YgY291cnNlLCBsYW5kIHBsb3RzIGNhbm5vdCBiZSByb3RhdGVkLCBpLmUuLCBpZiBGYXJtZXIgSm9obiBidXlzIGEgM3g1IHBsb3QgYW5kIGEgNXgzIHBsb3QgaW4gYSBncm91cCwgaGUgd2lsbCBwYXkgNXg1PTI1LjxcL3A+XHJcblxyXG48cD5GSiB3YW50cyB0byBncm93IGhpcyBmYXJtIGFzIG11Y2ggYXMgcG9zc2libGUgYW5kIGRlc2lyZXMgYWxsIHRoZSBwbG90cyBvZiBsYW5kLiBCZWluZyBib3RoIGNsZXZlciBhbmQgZnJ1Z2FsLCBpdCBkYXducyBvbiBoaW0gdGhhdCBoZSBjYW4gcHVyY2hhc2UgdGhlIGxhbmQgaW4gc3VjY2Vzc2l2ZSBncm91cHMsIGNsZXZlcmx5IG1pbmltaXppbmcgdGhlIHRvdGFsIGNvc3QgYnkgZ3JvdXBpbmcgdmFyaW91cyBwbG90cyB0aGF0IGhhdmUgYWR2YW50YWdlb3VzIHdpZHRoIG9yIGxlbmd0aCB2YWx1ZXMuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBudW1iZXIgb2YgcGxvdHMgZm9yIHNhbGUgYW5kIHRoZSBkaW1lbnNpb25zIG9mIGVhY2gsIGRldGVybWluZSB0aGUgbWluaW11bSBhbW91bnQgZm9yIHdoaWNoIEZhcm1lciBKb2huIGNhbiBwdXJjaGFzZSBhbGw8XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiBOPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzEgZGVzY3JpYmVzIHBsb3QgaSB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IHdpZHRoX2kgYW5kIGxlbmd0aF9pPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBtaW5pbXVtIGFtb3VudCBuZWNlc3NhcnkgdG8gYnV5IGFsbCB0aGUgcGxvdHMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+VGhlIGZpcnN0IGdyb3VwIGNvbnRhaW5zIGEgMTAweDEgcGxvdCBhbmQgY29zdHMgMTAwLiBUaGUgbmV4dCBncm91cCBjb250YWlucyBhIDF4MTAwIHBsb3QgYW5kIGNvc3RzIDEwMC4gVGhlIGxhc3QgZ3JvdXAgY29udGFpbnMgYm90aCB0aGUgMjB4NSBwbG90IGFuZCB0aGUgMTV4MTUgcGxvdCBhbmQgY29zdHMgMzAwLiBUaGUgdG90YWwgY29zdCBpcyA1MDAsIHdoaWNoIGlzIG1pbmltYWwuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=