시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB204267449831.047%

문제

농부 상헌이는 선재의 부동산에서 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+XHViODVjIFx1YjllNFx1YWNhOFx1YzExYyBcdWQzMTRcdWM1NThcdWIyOTRcdWIzNzAsIFx1YzBhY1x1YzJlNCBcdWM2OTRcdWM5OTggXHVjMTIwXHVjN2FjXHViMjk0IFx1YzdhNVx1YzBhY1x1YWMwMCBcdWM3OTggXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVjMTkwXHViMmQ4XHVjNzc0IFx1YWUwOVx1ZDU1YyBcdWMxMjBcdWM3YWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJiMzZcdWM3NGMgXHVkNTYwXHVjNzc4IFx1ZDU4OVx1YzBhY1x1Yjk3YyBcdWQxYjVcdWQ1NzRcdWMxMWMgXHViNTQ1XHVjNzQ0IFx1ZDMxNFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWI1NDVcdWM3NDQgXHVjMGI0IFx1YjU0Y1x1YjI5NCwgKFx1ZDU3NFx1YjJmOSBcdWI1NDUgXHVjOTExIFc8c3ViPmk8XC9zdWI+XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMikgKiAoXHVkNTc0XHViMmY5IFx1YjU0NSBcdWM5MTEgSDxzdWI+aTxcL3N1Yj5cdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyKSBcdWM3M2NcdWI4NWMgXHVhYzAwXHVhY2E5XHVjNzQ0IFx1YjllNFx1YWUzNFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMwYzFcdWQ1Y2NcdWM3NzRcdWIyOTQgXHVjMTIwXHVjN2FjXHVjNzU4IFx1ZDU4OVx1YzBhY1x1YWMwMCBcdWI5ZTRcdWM2YjAgXHVjODhiXHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YzExYyBcdWI1NDVcdWM3NDQgXHVjMGI0IFx1YzkwMFx1YmU0NFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNWM4XHVjOWMwXHViOWNjLCBcdWI1NDVcdWM3NDQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YmIzNlx1YzViNFx1YzBhY1x1YjI5NFx1YzljMFx1YzVkMCBcdWI1MzBcdWI3N2MgXHVhYzAwXHVhY2E5XHVjNzc0IFx1Y2M5Y1x1Y2MyOFx1YjljY1x1YmNjNFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVhZTY4XHViMmViXHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNCEgXHVjMGMxXHVkNWNjXHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3M2NcdWI4NWMgXHViNTQ1XHVjNzQ0IFx1YmIzNlx1YzViNFx1YzExYyBcdWMwYjQgXHVhY2JkXHVjNmIwLCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQwIFx1YzViY1x1YjljOFx1Yzc3Y1x1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbHQ7PSBOICZsdDs9IDUwMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgVzxzdWI+aTxcL3N1Yj4sIEg8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmx0Oz0gVzxzdWI+aTxcL3N1Yj4sIEg8c3ViPmk8XC9zdWI+ICZsdDs9IDEwMDAwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjMGMxXHVkNWNjXHVjNzc0XHVhYzAwIFx1YjU0NVx1Yzc0NCBcdWMwYWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPigxKSBcLyAoNCkgXC8gKDIsIDMpIFx1YzczY1x1Yjg1YyBcdWI1NDVcdWM3NDQgXHViYjM2XHVjNWI0IFx1YzBhY1x1YmNmNFx1Yzc5MC4gXHVjMGMxXHVkNWNjXHVjNzc0XHViMjk0IDEwMCAqIDEgKyAyMCAqIDE1ICsgMSAqIDEwMCA9IDUwMFx1Yzc1OCBcdWFjMDBcdWFjYTlcdWM1ZDAgXHViNTQ1XHVjNzQ0IFx1YzBiNCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNjE3MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxhbmQgQWNxdWlzaXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGlzIGNvbnNpZGVyaW5nIGJ1eWluZyBtb3JlIGxhbmQgZm9yIHRoZSBmYXJtIGFuZCBoYXMgaGlzIGV5ZSBvbiBOICgxICZsdDs9IE4gJmx0Oz0gNTAsMDAwKSBhZGRpdGlvbmFsIHJlY3Rhbmd1bGFyIHBsb3RzLCBlYWNoIHdpdGggaW50ZWdlciBkaW1lbnNpb25zICgxICZsdDs9IHdpZHRoX2kgJmx0Oz0gMSwwMDAsMDAwOyAxICZsdDs9IGxlbmd0aF9pICZsdDs9IDEsMDAwLDAwMCkuPFwvcD5cclxuXHJcbjxwPklmIEZKIHdhbnRzIHRvIGJ1eSBhIHNpbmdsZSBwaWVjZSBvZiBsYW5kLCB0aGUgY29zdCBpcyAkMVwvc3F1YXJlIHVuaXQsIGJ1dCBzYXZpbmdzIGFyZSBhdmFpbGFibGUgZm9yIGxhcmdlIHB1cmNoYXNlcy4gSGUgY2FuIGJ1eSBhbnkgbnVtYmVyIG9mIHBsb3RzIG9mIGxhbmQgZm9yIGEgcHJpY2UgaW4gZG9sbGFycyB0aGF0IGlzIHRoZSB3aWR0aCBvZiB0aGUgd2lkZXN0IHBsb3QgdGltZXMgdGhlIGxlbmd0aCBvZiB0aGUgbG9uZ2VzdCBwbG90LiBPZiBjb3Vyc2UsIGxhbmQgcGxvdHMgY2Fubm90IGJlIHJvdGF0ZWQsIGkuZS4sIGlmIEZhcm1lciBKb2huIGJ1eXMgYSAzeDUgcGxvdCBhbmQgYSA1eDMgcGxvdCBpbiBhIGdyb3VwLCBoZSB3aWxsIHBheSA1eDU9MjUuPFwvcD5cclxuXHJcbjxwPkZKIHdhbnRzIHRvIGdyb3cgaGlzIGZhcm0gYXMgbXVjaCBhcyBwb3NzaWJsZSBhbmQgZGVzaXJlcyBhbGwgdGhlIHBsb3RzIG9mIGxhbmQuIEJlaW5nIGJvdGggY2xldmVyIGFuZCBmcnVnYWwsIGl0IGRhd25zIG9uIGhpbSB0aGF0IGhlIGNhbiBwdXJjaGFzZSB0aGUgbGFuZCBpbiBzdWNjZXNzaXZlIGdyb3VwcywgY2xldmVybHkgbWluaW1pemluZyB0aGUgdG90YWwgY29zdCBieSBncm91cGluZyB2YXJpb3VzIHBsb3RzIHRoYXQgaGF2ZSBhZHZhbnRhZ2VvdXMgd2lkdGggb3IgbGVuZ3RoIHZhbHVlcy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG51bWJlciBvZiBwbG90cyBmb3Igc2FsZSBhbmQgdGhlIGRpbWVuc2lvbnMgb2YgZWFjaCwgZGV0ZXJtaW5lIHRoZSBtaW5pbXVtIGFtb3VudCBmb3Igd2hpY2ggRmFybWVyIEpvaG4gY2FuIHB1cmNoYXNlIGFsbDxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IE48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTisxOiBMaW5lIGkrMSBkZXNjcmliZXMgcGxvdCBpIHdpdGggdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2Vyczogd2lkdGhfaSBhbmQgbGVuZ3RoX2k8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIG1pbmltdW0gYW1vdW50IG5lY2Vzc2FyeSB0byBidXkgYWxsIHRoZSBwbG90cy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5UaGUgZmlyc3QgZ3JvdXAgY29udGFpbnMgYSAxMDB4MSBwbG90IGFuZCBjb3N0cyAxMDAuIFRoZSBuZXh0IGdyb3VwIGNvbnRhaW5zIGEgMXgxMDAgcGxvdCBhbmQgY29zdHMgMTAwLiBUaGUgbGFzdCBncm91cCBjb250YWlucyBib3RoIHRoZSAyMHg1IHBsb3QgYW5kIHRoZSAxNXgxNSBwbG90IGFuZCBjb3N0cyAzMDAuIFRoZSB0b3RhbCBjb3N0IGlzIDUwMCwgd2hpY2ggaXMgbWluaW1hbC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO March 2008 Contest > Gold 1번

  • 문제를 번역한 사람: koosaga