시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB89022815232.688%

문제

상근이는 도서관에서 번 돈으로 서강대 곤자가 플라자에 레스토랑을 하나 열었다. 이 레스토랑에는 음식을 N종류 팔고 있고, 손님은 서로 다른 음식을 여러개 시킬 수 있다. 이때, 음식을 시키는 순서가 중요하다. 그 이유는 각 음식을 첫 번째로 시킬 때의 가격과 아닐 때의 가격이 다르기 때문이다. 즉, 모든 음식 i의 가격은 첫 번째로 시킬 때의 가격 Ai와 아닐 때의 가격 Bi 두가지가 있다.

배가 고픈 창영이는 상근이네 레스토랑에서 음식을 시켜먹으려고 한다. 이때, 1개, 2개, ..., N개 시킬 때 필요한 최소 가격을 각각 구하는 프로그램을 작성하시오. 같은 종류 음식을 여러 번 중복해서 주문할 수 없다.

입력

첫째 줄에 상근이네 레스토랑의 음식의 개수 N(2 ≤ N ≤ 500,000)이 주어진다. 다음 N개의 줄에는 각 음식의 가격 Ai와 Bi가 주어진다. (0 ≤ Ai, Bi ≤ 1,000,000,000)

출력

출력은 총 N개로 이루어져 있다. i번째 줄에는 음식을 i개 시킬 때 필요한 최소 가격을 출력한다.

예제 입력 1

3
10 5
9 3
10 5

예제 출력 1

9
13
18
  • 음식을 1개 시킬 때는, 2번을 시키면 된다. (9)
  • 음식을 2개 시킬 때는, 1번을 시키고, 2번을 시키면 된다. (10+3)
  • 음식을 3개 시킬 때는, 1번을 시키고, 2번, 3번을 시키면 된다. (10+3+5)

예제 입력 2

2
100 1
1 100

예제 출력 2

1
2

예제 입력 3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

예제 출력 3

1000000000
2000000000
3000000000
4000000000
5000000000
W3sicHJvYmxlbV9pZCI6IjI3ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViODA4XHVjMmE0XHVkMWEwXHViNzkxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViM2M0XHVjMTFjXHVhZDAwXHVjNWQwXHVjMTFjIFx1YmM4OCBcdWIzYzhcdWM3M2NcdWI4NWMgXHVjMTFjXHVhYzE1XHViMzAwIFx1YWNlNFx1Yzc5MFx1YWMwMCBcdWQ1MGNcdWI3N2NcdWM3OTBcdWM1ZDAgXHViODA4XHVjMmE0XHVkMWEwXHViNzkxXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM1ZjRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM1ZDBcdWIyOTQgXHVjNzRjXHVjMmRkXHVjNzQ0IE5cdWM4ODVcdWI5NTggXHVkMzE0XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjMTkwXHViMmQ4XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzVlY1x1YjdlY1x1YWMxYyBcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjMmRjXHVkMGE0XHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVhYzAxIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5XHVhY2ZjIFx1YzU0NFx1YjJkMCBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHViYWE4XHViNGUwIFx1Yzc0Y1x1YzJkZCBpXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0MCBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5IEE8c3ViPmk8XC9zdWI+XHVjNjQwIFx1YzU0NFx1YjJkMCBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5IEI8c3ViPmk8XC9zdWI+IFx1YjQ1MFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMFx1YWMwMCBcdWFjZTBcdWQ1MDggXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM1ZDBcdWMxMWMgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzJkY1x1Y2YxY1x1YmEzOVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgMVx1YWMxYywgMlx1YWMxYywgLi4uLCBOXHVhYzFjIFx1YzJkY1x1ZDBhYyBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWFjMDBcdWFjYTlcdWM3NDQgXHVhYzAxXHVhYzAxIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjMTlcdWM3NDAgXHVjODg1XHViOTU4IFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzkxMVx1YmNmNVx1ZDU3NFx1YzExYyBcdWM4ZmNcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1YjgwOFx1YzJhNFx1ZDFhMFx1Yjc5MVx1Yzc1OCBcdWM3NGNcdWMyZGRcdWM3NTggXHVhYzFjXHVjMjE4IE4oMiAmbGU7IE4gJmxlOyA1MDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjNzRjXHVjMmRkXHVjNzU4IFx1YWMwMFx1YWNhOSBBPHN1Yj5pPFwvc3ViPlx1YzY0MCBCPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVjZDFkIE5cdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzRjXHVjMmRkXHVjNzQ0IGlcdWFjMWMgXHVjMmRjXHVkMGFjIFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6Ijx1bD5cclxuXHQ8bGk+XHVjNzRjXHVjMmRkXHVjNzQ0IDFcdWFjMWMgXHVjMmRjXHVkMGFjIFx1YjU0Y1x1YjI5NCwgMlx1YmM4OFx1Yzc0NCBcdWMyZGNcdWQwYTRcdWJhNzQgXHViNDFjXHViMmU0LiAoOSk8XC9saT5cclxuXHQ8bGk+XHVjNzRjXHVjMmRkXHVjNzQ0IDJcdWFjMWMgXHVjMmRjXHVkMGFjIFx1YjU0Y1x1YjI5NCwgMVx1YmM4OFx1Yzc0NCBcdWMyZGNcdWQwYTRcdWFjZTAsIDJcdWJjODhcdWM3NDQgXHVjMmRjXHVkMGE0XHViYTc0IFx1YjQxY1x1YjJlNC4gKDEwKzMpPFwvbGk+XHJcblx0PGxpPlx1Yzc0Y1x1YzJkZFx1Yzc0NCAzXHVhYzFjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWIyOTQsIDFcdWJjODhcdWM3NDQgXHVjMmRjXHVkMGE0XHVhY2UwLCAyXHViYzg4LCAzXHViYzg4XHVjNzQ0IFx1YzJkY1x1ZDBhNFx1YmE3NCBcdWI0MWNcdWIyZTQuICgxMCszKzUpPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIyNzg2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUE9QVVNUIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBpcyBodW5ncnkgYXMgYSBiZWFyLCBzY3JhdGNoIHRoYXQsIHByb2dyYW1tZXIgYW5kIGhhcyBzdHVtYmxlZCB1cG9uIGEgbG9jYWwgcmVzdGF1cmFudC4gVGhlIHJlc3RhdXJhbnQgb2ZmZXJzIE4gbWVhbHMgYW5kIGhhcyBhbiBpbnRlcmVzdGluZyBwcmljaW5nIHBvbGljeTogZWFjaCBtZWFsIGkgaGFzIHR3byBhc3NpZ25lZCBwcmljZXMsIEE8c3ViPmk8XC9zdWI+IGFuZCBCPHN1Yj5pPFwvc3ViPi4gTWlya28gcGF5cyBBIG9ubHkgZm9yIHRoZSBmaXJzdCBvcmRlcmVkIG1lYWwsIHdoaWxlIEIgcHJpY2VzIGFwcGx5IGZvciBhbGwgb3RoZXIgbWVhbHMuPFwvcD5cclxuXHJcbjxwPk1pa3JvIGNhbiYjMzk7dCBkZWNpZGUgaG93IG1hbnkgbWVhbHMgdG8gb3JkZXIuIEluIG9yZGVyIHRvIG1ha2UgaGlzIGRlY2lzaW9uIGVhc2llciwgaGUgaGFzIGFza2VkIHlvdSB0byBjb21wdXRlLCBmb3IgZWFjaCBrIGJldHdlZW4gMSBpIE4gKGluY2x1c2l2ZSksIHRoZSBtaW5pbXVtIHRvdGFsIHByaWNlIGZvciBrIG9yZGVyZWQgbWVhbHMuIE1pcmtvIGRvZXNuJiMzOTt0IGNhcmUgd2hpY2ggcGFydGljdWxhciBtZWFscyBoZSBvcmRlcnMgb3IgaW4gd2hpY2ggb3JkZXIgaGUgb3JkZXJzIHRoZW0sIGhvd2V2ZXIgaGUgd29uJiMzOTt0IG9yZGVyIHRoZSBzYW1lIG1lYWwgdHdpY2UuIE9yZGVyLCBvcmRlciwgb3JkZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDUwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBtZWFscyBvZmZlcmVkIGJ5IHRoZSByZXN0YXVyYW50LjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMsIEE8c3ViPmk8XC9zdWI+IGFuZCBCPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IEE8c3ViPmk8XC9zdWI+LCBCPHN1Yj5pPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDApLCB0aGUgcHJpY2VzIGZvciBtZWFsIGkgYXMgZGVzY3JpYmVkIGFib3ZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBtdXN0IGNvbnNpc3Qgb2YgTiBsaW5lcywgd2hlcmUgbGluZSBrIGNvbnRhaW5zIHRoZSBtaW5pbXVtIHByaWNlIGZvciBvcmRlcmluZyBleGFjdGx5IGsgZGlmZmVyZW50IG1lYWxzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHVsPlxyXG5cdDxsaT5rID0gMTogTWlya28gcGF5cyBBMiA9IDkgZm9yIHRoZSBzdGFydGluZyBtZWFsIDIuPFwvbGk+XHJcblx0PGxpPmsgPSAyOiBNaXJrbyBwYXlzIEExID0gMTAgZm9yIHRoZSBzdGFydGluZyBtZWFsIDEsIHRoZW4gQjIgPSAzIGZvciBtZWFsIDIuPFwvbGk+XHJcblx0PGxpPmsgPSAzOiBNaXJrbyBwYXlzIEExID0gMTAgZm9yIHRoZSBzdGFydGluZyBtZWFsIDEsIHRoZW4gQjIgPSAzIGZvciBtZWFsIDIsIGFuZCBmaW5hbGx5IEIzPSA1IGZvciBtZWFsIDMuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #2 4번