시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 366 123 64 38.788%

문제

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

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

입력

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

W3sicHJvYmxlbV9pZCI6IjI3ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViODA4XHVjMmE0XHVkMWEwXHViNzkxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViM2M0XHVjMTFjXHVhZDAwXHVjNWQwXHVjMTFjIFx1YmM4OCBcdWIzYzhcdWM3M2NcdWI4NWMgXHVjMTFjXHVhYzE1XHViMzAwIFx1YWNlNFx1Yzc5MFx1YWMwMCBcdWQ1MGNcdWI3N2NcdWM3OTBcdWM1ZDAgXHViODA4XHVjMmE0XHVkMWEwXHViNzkxXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM1ZjRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM1ZDBcdWIyOTQgXHVjNzRjXHVjMmRkXHVjNzQ0IE5cdWM4ODVcdWI5NTggXHVkMzE0XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjMTkwXHViMmQ4XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzVlY1x1YjdlY1x1YWMxYyBcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjMmRjXHVkMGE0XHViMjk0IFx1YzIxY1x1YzExY1x1YWMwMCBcdWM5MTFcdWM2OTRcdWQ1NThcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVhYzAxIFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5XHVhY2ZjIFx1YzU0NFx1YjJkMCBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHViYWE4XHViNGUwIFx1Yzc0Y1x1YzJkZCBpXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0MCBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5IEE8c3ViPmk8XC9zdWI+XHVjNjQwIFx1YzU0NFx1YjJkMCBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5IEI8c3ViPmk8XC9zdWI+IFx1YjQ1MFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMFx1YWMwMCBcdWFjZTBcdWQ1MDggXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM1ZDBcdWMxMWMgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzJkY1x1Y2YxY1x1YmEzOVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgMVx1YWMxYywgMlx1YWMxYywgLi4uLCBOXHVhYzFjIFx1YzJkY1x1ZDBhYyBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWFjMDBcdWFjYTlcdWM3NDQgXHVhYzAxXHVhYzAxIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjMTlcdWM3NDAgXHVjODg1XHViOTU4IFx1Yzc0Y1x1YzJkZFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzkxMVx1YmNmNVx1ZDU3NFx1YzExYyBcdWM4ZmNcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1YjgwOFx1YzJhNFx1ZDFhMFx1Yjc5MVx1Yzc1OCBcdWM3NGNcdWMyZGRcdWM3NTggXHVhYzFjXHVjMjE4IE4oMiAmbGU7IE4gJmxlOyA1MDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjNzRjXHVjMmRkXHVjNzU4IFx1YWMwMFx1YWNhOSBBPHN1Yj5pPFwvc3ViPlx1YzY0MCBCPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVjZDFkIE5cdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzRjXHVjMmRkXHVjNzQ0IGlcdWFjMWMgXHVjMmRjXHVkMGFjIFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Yzc0Y1x1YzJkZFx1Yzc0NCAxXHVhYzFjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWIyOTQsIDJcdWJjODhcdWM3NDQgXHVjMmRjXHVkMGE0XHViYTc0IFx1YjQxY1x1YjJlNC4gKDkpPFwvcD5cclxuXHJcbjxwPlx1Yzc0Y1x1YzJkZFx1Yzc0NCAyXHVhYzFjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWIyOTQsIDFcdWJjODhcdWM3NDQgXHVjMmRjXHVkMGE0XHVhY2UwLCAyXHViYzg4XHVjNzQ0IFx1YzJkY1x1ZDBhNFx1YmE3NCBcdWI0MWNcdWIyZTQuICgxMCszKTxcL3A+XHJcblxyXG48cD5cdWM3NGNcdWMyZGRcdWM3NDQgM1x1YWMxYyBcdWMyZGNcdWQwYWMgXHViNTRjXHViMjk0LCAxXHViYzg4XHVjNzQ0IFx1YzJkY1x1ZDBhNFx1YWNlMCwgMlx1YmM4OCwgM1x1YmM4OFx1Yzc0NCBcdWMyZGNcdWQwYTRcdWJhNzQgXHViNDFjXHViMmU0LiAoMTArMys1KTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBPUFVTVCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaXMgaHVuZ3J5IGFzIGEgYmVhciwgc2NyYXRjaCB0aGF0LCBwcm9ncmFtbWVyIGFuZCBoYXMgc3R1bWJsZWQgdXBvbiBhIGxvY2FsIHJlc3RhdXJhbnQuIFRoZSByZXN0YXVyYW50IG9mZmVycyBOIG1lYWxzIGFuZCBoYXMgYW4gaW50ZXJlc3RpbmcgcHJpY2luZyBwb2xpY3k6IGVhY2ggbWVhbCBpIGhhcyB0d28gYXNzaWduZWQgcHJpY2VzLCBBPHN1Yj5pPFwvc3ViPiBhbmQgQjxzdWI+aTxcL3N1Yj4uIE1pcmtvIHBheXMgQSBvbmx5IGZvciB0aGUgZmlyc3Qgb3JkZXJlZCBtZWFsLCB3aGlsZSBCIHByaWNlcyBhcHBseSBmb3IgYWxsIG90aGVyIG1lYWxzLjxcL3A+XHJcblxyXG48cD5NaWtybyBjYW4mIzM5O3QgZGVjaWRlIGhvdyBtYW55IG1lYWxzIHRvIG9yZGVyLiBJbiBvcmRlciB0byBtYWtlIGhpcyBkZWNpc2lvbiBlYXNpZXIsIGhlIGhhcyBhc2tlZCB5b3UgdG8gY29tcHV0ZSwgZm9yIGVhY2ggayBiZXR3ZWVuIDEgaSBOIChpbmNsdXNpdmUpLCB0aGUgbWluaW11bSB0b3RhbCBwcmljZSBmb3IgayBvcmRlcmVkIG1lYWxzLiBNaXJrbyBkb2VzbiYjMzk7dCBjYXJlIHdoaWNoIHBhcnRpY3VsYXIgbWVhbHMgaGUgb3JkZXJzIG9yIGluIHdoaWNoIG9yZGVyIGhlIG9yZGVycyB0aGVtLCBob3dldmVyIGhlIHdvbiYjMzk7dCBvcmRlciB0aGUgc2FtZSBtZWFsIHR3aWNlLiBPcmRlciwgb3JkZXIsIG9yZGVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyA1MDAgMDAwKSwgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgbWVhbHMgb2ZmZXJlZCBieSB0aGUgcmVzdGF1cmFudC48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzLCBBPHN1Yj5pPFwvc3ViPiBhbmQgQjxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBBPHN1Yj5pPFwvc3ViPiwgQjxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwKSwgdGhlIHByaWNlcyBmb3IgbWVhbCBpIGFzIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgbXVzdCBjb25zaXN0IG9mIE4gbGluZXMsIHdoZXJlIGxpbmUgayBjb250YWlucyB0aGUgbWluaW11bSBwcmljZSBmb3Igb3JkZXJpbmcgZXhhY3RseSBrIGRpZmZlcmVudCBtZWFscy48XC9wPlxyXG4iLCJoaW50IjoiPHA+ayA9IDE6IE1pcmtvIHBheXMgQTIgPSA5IGZvciB0aGUgc3RhcnRpbmcgbWVhbCAyLjxiciBcLz5cclxuayA9IDI6IE1pcmtvIHBheXMgQTEgPSAxMCBmb3IgdGhlIHN0YXJ0aW5nIG1lYWwgMSwgdGhlbiBCMiA9IDMgZm9yIG1lYWwgMi48YnIgXC8+XHJcbmsgPSAzOiBNaXJrbyBwYXlzIEExID0gMTAgZm9yIHRoZSBzdGFydGluZyBtZWFsIDEsIHRoZW4gQjIgPSAzIGZvciBtZWFsIDIsIGFuZCBmaW5hbGx5IEIzPSA1IGZvciBtZWFsIDMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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