시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 367 90 64 24.335%

문제

농부 상헌이는 선재의 부동산에서 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+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IE4gJmx0Oz0gNTAwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBXPHN1Yj5pPFwvc3ViPiwgSDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbHQ7PSBXPHN1Yj5pPFwvc3ViPiwgSDxzdWI+aTxcL3N1Yj4gJmx0Oz0gMTAwMDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYzFcdWQ1Y2NcdWM3NzRcdWFjMDAgXHViNTQ1XHVjNzQ0IFx1YzBhY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+KDEpIFwvICg0KSBcLyAoMiwgMykgXHVjNzNjXHViODVjIFx1YjU0NVx1Yzc0NCBcdWJiMzZcdWM1YjQgXHVjMGFjXHViY2Y0XHVjNzkwLiBcdWMwYzFcdWQ1Y2NcdWM3NzRcdWIyOTQgMTAwICogMSArIDIwICogMTUgKyAxICogMTAwID0gNTAwXHVjNzU4IFx1YWMwMFx1YWNhOVx1YzVkMCBcdWI1NDVcdWM3NDQgXHVjMGI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2MTcxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGFuZCBBY3F1aXNpdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaXMgY29uc2lkZXJpbmcgYnV5aW5nIG1vcmUgbGFuZCBmb3IgdGhlIGZhcm0gYW5kIGhhcyBoaXMgZXllIG9uIE4gKDEgJmx0Oz0gTiAmbHQ7PSA1MCwwMDApIGFkZGl0aW9uYWwgcmVjdGFuZ3VsYXIgcGxvdHMsIGVhY2ggd2l0aCBpbnRlZ2VyIGRpbWVuc2lvbnMgKDEgJmx0Oz0gd2lkdGhfaSAmbHQ7PSAxLDAwMCwwMDA7IDEgJmx0Oz0gbGVuZ3RoX2kgJmx0Oz0gMSwwMDAsMDAwKS48XC9wPlxyXG5cclxuPHA+SWYgRkogd2FudHMgdG8gYnV5IGEgc2luZ2xlIHBpZWNlIG9mIGxhbmQsIHRoZSBjb3N0IGlzICQxXC9zcXVhcmUgdW5pdCwgYnV0IHNhdmluZ3MgYXJlIGF2YWlsYWJsZSBmb3IgbGFyZ2UgcHVyY2hhc2VzLiBIZSBjYW4gYnV5IGFueSBudW1iZXIgb2YgcGxvdHMgb2YgbGFuZCBmb3IgYSBwcmljZSBpbiBkb2xsYXJzIHRoYXQgaXMgdGhlIHdpZHRoIG9mIHRoZSB3aWRlc3QgcGxvdCB0aW1lcyB0aGUgbGVuZ3RoIG9mIHRoZSBsb25nZXN0IHBsb3QuIE9mIGNvdXJzZSwgbGFuZCBwbG90cyBjYW5ub3QgYmUgcm90YXRlZCwgaS5lLiwgaWYgRmFybWVyIEpvaG4gYnV5cyBhIDN4NSBwbG90IGFuZCBhIDV4MyBwbG90IGluIGEgZ3JvdXAsIGhlIHdpbGwgcGF5IDV4NT0yNS48XC9wPlxyXG5cclxuPHA+Rkogd2FudHMgdG8gZ3JvdyBoaXMgZmFybSBhcyBtdWNoIGFzIHBvc3NpYmxlIGFuZCBkZXNpcmVzIGFsbCB0aGUgcGxvdHMgb2YgbGFuZC4gQmVpbmcgYm90aCBjbGV2ZXIgYW5kIGZydWdhbCwgaXQgZGF3bnMgb24gaGltIHRoYXQgaGUgY2FuIHB1cmNoYXNlIHRoZSBsYW5kIGluIHN1Y2Nlc3NpdmUgZ3JvdXBzLCBjbGV2ZXJseSBtaW5pbWl6aW5nIHRoZSB0b3RhbCBjb3N0IGJ5IGdyb3VwaW5nIHZhcmlvdXMgcGxvdHMgdGhhdCBoYXZlIGFkdmFudGFnZW91cyB3aWR0aCBvciBsZW5ndGggdmFsdWVzLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbnVtYmVyIG9mIHBsb3RzIGZvciBzYWxlIGFuZCB0aGUgZGltZW5zaW9ucyBvZiBlYWNoLCBkZXRlcm1pbmUgdGhlIG1pbmltdW0gYW1vdW50IGZvciB3aGljaCBGYXJtZXIgSm9obiBjYW4gcHVyY2hhc2UgYWxsPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlcjogTjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5OKzE6IExpbmUgaSsxIGRlc2NyaWJlcyBwbG90IGkgd2l0aCB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiB3aWR0aF9pIGFuZCBsZW5ndGhfaTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbWluaW11bSBhbW91bnQgbmVjZXNzYXJ5IHRvIGJ1eSBhbGwgdGhlIHBsb3RzLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IjxwPlRoZSBmaXJzdCBncm91cCBjb250YWlucyBhIDEwMHgxIHBsb3QgYW5kIGNvc3RzIDEwMC4gVGhlIG5leHQgZ3JvdXAgY29udGFpbnMgYSAxeDEwMCBwbG90IGFuZCBjb3N0cyAxMDAuIFRoZSBsYXN0IGdyb3VwIGNvbnRhaW5zIGJvdGggdGhlIDIweDUgcGxvdCBhbmQgdGhlIDE1eDE1IHBsb3QgYW5kIGNvc3RzIDMwMC4gVGhlIHRvdGFsIGNvc3QgaXMgNTAwLCB3aGljaCBpcyBtaW5pbWFsLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d