시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1159 352 272 33.622%

문제

한 저명한 학자에게 n(0≤n≤10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1≤d≤10,000)일 안에 와서 강연을 해 주면 p(1≤p≤10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

예제 입력 1

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

예제 출력 1

185
W3sicHJvYmxlbV9pZCI6IjIxMDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWQ2OGNcdWFjMTVcdWM1ZjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1YyBcdWM4MDBcdWJhODVcdWQ1NWMgXHVkNTU5XHVjNzkwXHVjNWQwXHVhYzhjIG4oMCZsZTtuJmxlOzEwLDAwMClcdWFjMWNcdWM3NTggXHViMzAwXHVkNTU5XHVjNWQwXHVjMTFjIFx1YWMxNVx1YzVmMCBcdWM2OTRcdWNjYWRcdWM3NDQgXHVkNTc0IFx1YzY1NFx1YjJlNC4gXHVhYzAxIFx1YjMwMFx1ZDU1OVx1YzVkMFx1YzExY1x1YjI5NCBkKDEmbGU7ZCZsZTsxMCwwMDApXHVjNzdjIFx1YzU0OFx1YzVkMCBcdWM2NDBcdWMxMWMgXHVhYzE1XHVjNWYwXHVjNzQ0IFx1ZDU3NCBcdWM4ZmNcdWJhNzQgcCgxJmxlO3AmbGU7MTAsMDAwKVx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWFjMTVcdWM1ZjBcdWI4Y2NcdWI5N2MgXHVjOWMwXHViZDg4XHVkNTU4XHVhY2EwXHViMmU0XHVhY2UwIFx1YzU0Y1x1YjgyNFx1YzY1NFx1YjJlNC4gXHVhYzAxIFx1YjMwMFx1ZDU1OVx1YzVkMFx1YzExYyBcdWM4MWNcdWMyZGNcdWQ1NThcdWIyOTQgZFx1YzY0MCBwXHVhYzEyXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1ZDU1OVx1Yzc5MFx1YjI5NCBcdWM3NzRcdWI5N2MgXHViYzE0XHVkMGQ1XHVjNzNjXHViODVjLCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YjNjOFx1Yzc0NCBcdWJjOGMgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWMyMWNcdWQ2OGNcdWFjMTVcdWM1ZjBcdWM3NDQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVhYzE1XHVjNWYwXHVjNzU4IFx1ZDJiOVx1YzEzMVx1YzBjMSwgXHVjNzc0IFx1ZDU1OVx1Yzc5MFx1YjI5NCBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWFjZjNcdWM1ZDBcdWMxMWNcdWI5Y2MgXHVhYzE1XHVjNWYwXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViMTI0IFx1YjMwMFx1ZDU1OVx1YzVkMFx1YzExYyBcdWM4MWNcdWMyZGNcdWQ1NWMgcFx1YWMxMlx1Yzc3NCBcdWFjMDFcdWFjMDEgNTAsIDEwLCAyMCwgMzBcdWM3NzRcdWFjZTAsIGRcdWFjMTJcdWM3NzQgXHVjYzI4XHViODQwXHViODVjIDIsIDEsIDIsIDEgXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViN2Y0IFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWNjYWJcdWM5ZjggXHViMGEwXHVjNWQwIDRcdWJjODggXHViMzAwXHVkNTU5XHVjNWQwXHVjMTFjIFx1YWMxNVx1YzVmMFx1Yzc0NCBcdWQ1NThcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWIwYTBcdWM1ZDAgMVx1YmM4OCBcdWIzMDBcdWQ1NTlcdWM1ZDBcdWMxMWMgXHVhYzE1XHVjNWYwXHVjNzQ0IFx1ZDU1OFx1YmE3NCA4MFx1YjljY1x1ZDA3Y1x1Yzc1OCBcdWIzYzhcdWM3NDQgXHViYzhjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjMwMFx1ZDU1OVx1YzVkMFx1YzExYyBcdWM4MWNcdWMyZGNcdWQ1NWMgcFx1YWMxMlx1YWNmYyBkXHVhYzEyXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwXHViODVjIFx1YmM4YyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjNjOFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMTA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3VwZXJtYXJrZXQiLCJkZXNjcmlwdGlvbiI6IjxwPkEgc3VwZXJtYXJrZXQgaGFzIGEgc2V0IFByb2Qgb2YgcHJvZHVjdHMgb24gc2FsZS4gSXQgZWFybnMgYSBwcm9maXQgcDxzdWI+eDxcL3N1Yj4gZm9yIGVhY2ggcHJvZHVjdCB4JmlzaW47UHJvZCBzb2xkIGJ5IGEgZGVhZGxpbmUgZDxzdWI+eDxcL3N1Yj4gdGhhdCBpcyBtZWFzdXJlZCBhcyBhbiBpbnRlZ3JhbCBudW1iZXIgb2YgdGltZSB1bml0cyBzdGFydGluZyBmcm9tIHRoZSBtb21lbnQgdGhlIHNhbGUgYmVnaW5zLiBFYWNoIHByb2R1Y3QgdGFrZXMgcHJlY2lzZWx5IG9uZSB1bml0IG9mIHRpbWUgZm9yIGJlaW5nIHNvbGQuIEEgc2VsbGluZyBzY2hlZHVsZSBpcyBhbiBvcmRlcmVkIHN1YnNldCBvZiBwcm9kdWN0cyBTZWxsJnN1YmU7UHJvZCBzdWNoIHRoYXQgdGhlIHNlbGxpbmcgb2YgZWFjaCBwcm9kdWN0IHgmaXNpbjtTZWxsLCBhY2NvcmRpbmcgdG8gdGhlIG9yZGVyaW5nIG9mIFNlbGwsIGNvbXBsZXRlcyBiZWZvcmUgdGhlIGRlYWRsaW5lIGQ8c3ViPng8XC9zdWI+IG9yIGp1c3Qgd2hlbiBkPHN1Yj54PFwvc3ViPiBleHBpcmVzLiBUaGUgcHJvZml0IG9mIHRoZSBzZWxsaW5nIHNjaGVkdWxlIGlzIFByb2ZpdChTZWxsKT0mc3VtOzxzdWI+eCZpc2luO1NlbGw8XC9zdWI+IHA8c3ViPng8XC9zdWI+IC4gQW4gb3B0aW1hbCBzZWxsaW5nIHNjaGVkdWxlIGlzIGEgc2NoZWR1bGUgd2l0aCBhIG1heGltdW0gcHJvZml0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgY29uc2lkZXIgdGhlIHByb2R1Y3RzIFByb2Q9e2EsYixjLGR9IHdpdGggKHA8c3ViPmE8XC9zdWI+LGQ8c3ViPmE8XC9zdWI+KT0oNTAsMiksIChwPHN1Yj5iPFwvc3ViPixkPHN1Yj5iPFwvc3ViPik9KDEwLDEpLCAocDxzdWI+YzxcL3N1Yj4sZDxzdWI+YzxcL3N1Yj4pPSgyMCwyKSwgYW5kIChwPHN1Yj5kPFwvc3ViPixkPHN1Yj5kPFwvc3ViPik9KDMwLDEpLiBUaGUgcG9zc2libGUgc2VsbGluZyBzY2hlZHVsZXMgYXJlIGxpc3RlZCBpbiB0YWJsZSAxLiBGb3IgaW5zdGFuY2UsIHRoZSBzY2hlZHVsZSBTZWxsPXtkLGF9IHNob3dzIHRoYXQgdGhlIHNlbGxpbmcgb2YgcHJvZHVjdCBkIHN0YXJ0cyBhdCB0aW1lIDAgYW5kIGVuZHMgYXQgdGltZSAxLCB3aGlsZSB0aGUgc2VsbGluZyBvZiBwcm9kdWN0IGEgc3RhcnRzIGF0IHRpbWUgMSBhbmQgZW5kcyBhdCB0aW1lIDIuIEVhY2ggb2YgdGhlc2UgcHJvZHVjdHMgaXMgc29sZCBieSBpdHMgZGVhZGxpbmUuIFNlbGwgaXMgdGhlIG9wdGltYWwgc2NoZWR1bGUgYW5kIGl0cyBwcm9maXQgaXMgODAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHJlYWRzIHNldHMgb2YgcHJvZHVjdHMgZnJvbSBhbiBpbnB1dCB0ZXh0IGZpbGUgYW5kIGNvbXB1dGVzIHRoZSBwcm9maXQgb2YgYW4gb3B0aW1hbCBzZWxsaW5nIHNjaGVkdWxlIGZvciBlYWNoIHNldCBvZiBwcm9kdWN0cy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkEgc2V0IG9mIHByb2R1Y3RzIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgMCZsZTtuJmxlOzEwMDAwLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIHByb2R1Y3RzIGluIHRoZSBzZXQsIGFuZCBjb250aW51ZXMgd2l0aCBuIHBhaXJzIHA8c3ViPmk8XC9zdWI+IGQ8c3ViPmk8XC9zdWI+IG9mIGludGVnZXJzLCAxJmxlO3A8c3ViPmk8XC9zdWI+JmxlOzEwMDAwIGFuZCAxJmxlO2Q8c3ViPmk8XC9zdWI+JmxlOzEwMDAwLCB0aGF0IGRlc2lnbmF0ZSB0aGUgcHJvZml0IGFuZCB0aGUgc2VsbGluZyBkZWFkbGluZSBvZiB0aGUgaS10aCBwcm9kdWN0LiBXaGl0ZSBzcGFjZXMgY2FuIG9jY3VyIGZyZWVseSBpbiBpbnB1dC4gSW5wdXQgZGF0YSB0ZXJtaW5hdGUgd2l0aCBhbiBlbmQgb2YgZmlsZSBhbmQgYXJlIGd1YXJhbnRlZWQgY29ycmVjdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBzZXQgb2YgcHJvZHVjdHMsIHRoZSBwcm9ncmFtIHByaW50cyBvbiB0aGUgc3RhbmRhcmQgb3V0cHV0IHRoZSBwcm9maXQgb2YgYW4gb3B0aW1hbCBzZWxsaW5nIHNjaGVkdWxlIGZvciB0aGUgc2V0LiBFYWNoIHJlc3VsdCBpcyBwcmludGVkIGZyb20gdGhlIGJlZ2lubmluZyBvZiBhIHNlcGFyYXRlIGxpbmUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d