시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 337 115 57 39.583%

문제

상근이는 도서관에서 번 돈으로 서강대 곤자가 플라자에 레스토랑을 하나 열었다. 이 레스토랑에는 음식을 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)

W3sicHJvYmxlbV9pZCI6IjI3ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViODA4XHVjMmE0XHVkMWEwXHViNzkxIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViM2M0XHVjMTFjXHVhZDAwXHVjNWQwXHVjMTFjIFx1YmM4OCBcdWIzYzhcdWM3M2NcdWI4NWMgXHVjMTFjXHVhYzE1XHViMzAwIFx1YWNlNFx1Yzc5MFx1YWMwMCBcdWQ1MGNcdWI3N2NcdWM3OTBcdWM1ZDAgXHViODA4XHVjMmE0XHVkMWEwXHViNzkxXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWM1ZjRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM1ZDBcdWIyOTQgXHVjNzRjXHVjMmRkXHVjNzQ0IE5cdWFjMWMgXHVkMzE0XHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjMTkwXHViMmQ4XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzVlY1x1YjdlY1x1YWMxYyBcdWMyZGNcdWQwYWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzJkY1x1ZDBhNFx1YjI5NCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjOTExXHVjNjk0XHVkNTU4XHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IFx1YWMwMSBcdWM3NGNcdWMyZGRcdWM3NDQgXHVjY2FiXHViYzg4XHVjOWY4XHViODVjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5XHVhY2ZjIFx1YzU0NFx1YjJkMCBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHViYWE4XHViNGUwIFx1Yzc0Y1x1YzJkZCBpXHVjNzU4IFx1YWMwMFx1YWNhOVx1Yzc0MCBcdWNjYWIgXHViYzg4XHVjOWY4XHViODVjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5IEE8c3ViPmk8XC9zdWI+XHVjNjQwIFx1YzU0NFx1YjJkMCBcdWI1NGNcdWM3NTggXHVhYzAwXHVhY2E5IEI8c3ViPmk8XC9zdWI+IFx1YjQ1MFx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YmMzMFx1YWMwMCBcdWFjZTBcdWQ1MDggXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWI4MDhcdWMyYTRcdWQxYTBcdWI3OTFcdWM1ZDBcdWMxMWMgXHVjNzRjXHVjMmRkXHVjNzQ0IFx1YzJkY1x1Y2YxY1x1YmEzOVx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIDFcdWFjMWMsIDJcdWFjMWMsIC4uLiwgTlx1YWMxYyBcdWMyZGNcdWQwYWMgXHViNTRjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVhYzAwXHVhY2E5XHVjNzQ0IFx1YWMwMVx1YWMwMSBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1YjgwOFx1YzJhNFx1ZDFhMFx1Yjc5MVx1Yzc1OCBcdWM3NGNcdWMyZGRcdWM3NTggXHVhYzFjXHVjMjE4IE4oMiAmbGU7IE4gJmxlOyA1MDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjNzRjXHVjMmRkXHVjNzU4IFx1YWMwMFx1YWNhOSBBPHN1Yj5pPFwvc3ViPlx1YzY0MCBCPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNkOWNcdWI4MjVcdWM3NDAgXHVjZDFkIE5cdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzRjXHVjMmRkXHVjNzQ0IGlcdWFjMWMgXHVjMmRjXHVkMGFjIFx1YjU0YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YWMwMFx1YWNhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1Yzc0Y1x1YzJkZFx1Yzc0NCAxXHVhYzFjIFx1YzJkY1x1ZDBhYyBcdWI1NGNcdWIyOTQsIDJcdWJjODhcdWM3NDQgXHVjMmRjXHVkMGE0XHViYTc0IFx1YjQxY1x1YjJlNC4gKDkpPFwvcD5cclxuPHA+XHJcblx0XHVjNzRjXHVjMmRkXHVjNzQ0IDJcdWFjMWMgXHVjMmRjXHVkMGFjIFx1YjU0Y1x1YjI5NCwgMVx1YmM4OFx1Yzc0NCBcdWMyZGNcdWQwYTRcdWFjZTAsIDJcdWJjODhcdWM3NDQgXHVjMmRjXHVkMGE0XHViYTc0IFx1YjQxY1x1YjJlNC4gKDEwKzMpPFwvcD5cclxuPHA+XHJcblx0XHVjNzRjXHVjMmRkXHVjNzQ0IDNcdWFjMWMgXHVjMmRjXHVkMGFjIFx1YjU0Y1x1YjI5NCwgMVx1YmM4OFx1Yzc0NCBcdWMyZGNcdWQwYTRcdWFjZTAsIDJcdWJjODgsIDNcdWJjODhcdWM3NDQgXHVjMmRjXHVkMGE0XHViYTc0IFx1YjQxY1x1YjJlNC4gKDEwKzMrNSk8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3ODYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQT1BVU1QiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGlzIGh1bmdyeSBhcyBhIGJlYXIsIHNjcmF0Y2ggdGhhdCwgcHJvZ3JhbW1lciBhbmQgaGFzIHN0dW1ibGVkIHVwb24gYSBsb2NhbCByZXN0YXVyYW50LiBUaGUgcmVzdGF1cmFudCBvZmZlcnMgTiBtZWFscyBhbmQgaGFzIGFuIGludGVyZXN0aW5nIHByaWNpbmcgcG9saWN5OiBlYWNoIG1lYWwgaSBoYXMgdHdvIGFzc2lnbmVkIHByaWNlcywgQTxzdWI+aTxcL3N1Yj4gYW5kIEI8c3ViPmk8XC9zdWI+LiBNaXJrbyBwYXlzIEEgb25seSBmb3IgdGhlIGZpcnN0IG9yZGVyZWQgbWVhbCwgd2hpbGUgQiBwcmljZXMgYXBwbHkgZm9yIGFsbCBvdGhlciBtZWFscy48XC9wPlxyXG5cclxuPHA+TWlrcm8gY2FuJiMzOTt0IGRlY2lkZSBob3cgbWFueSBtZWFscyB0byBvcmRlci4gSW4gb3JkZXIgdG8gbWFrZSBoaXMgZGVjaXNpb24gZWFzaWVyLCBoZSBoYXMgYXNrZWQgeW91IHRvIGNvbXB1dGUsIGZvciBlYWNoIGsgYmV0d2VlbiAxIGkgTiAoaW5jbHVzaXZlKSwgdGhlIG1pbmltdW0gdG90YWwgcHJpY2UgZm9yIGsgb3JkZXJlZCBtZWFscy4gTWlya28gZG9lc24mIzM5O3QgY2FyZSB3aGljaCBwYXJ0aWN1bGFyIG1lYWxzIGhlIG9yZGVycyBvciBpbiB3aGljaCBvcmRlciBoZSBvcmRlcnMgdGhlbSwgaG93ZXZlciBoZSB3b24mIzM5O3Qgb3JkZXIgdGhlIHNhbWUgbWVhbCB0d2ljZS4gT3JkZXIsIG9yZGVyLCBvcmRlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgNTAwIDAwMCksIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IG1lYWxzIG9mZmVyZWQgYnkgdGhlIHJlc3RhdXJhbnQuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgQTxzdWI+aTxcL3N1Yj4gYW5kIEI8c3ViPmk8XC9zdWI+ICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4sIEI8c3ViPmk8XC9zdWI+ICZsZTsgMSAwMDAgMDAwIDAwMCksIHRoZSBwcmljZXMgZm9yIG1lYWwgaSBhcyBkZXNjcmliZWQgYWJvdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG11c3QgY29uc2lzdCBvZiBOIGxpbmVzLCB3aGVyZSBsaW5lIGsgY29udGFpbnMgdGhlIG1pbmltdW0gcHJpY2UgZm9yIG9yZGVyaW5nIGV4YWN0bHkgayBkaWZmZXJlbnQgbWVhbHMuPFwvcD5cclxuIiwiaGludCI6IjxwPmsgPSAxOiBNaXJrbyBwYXlzIEEyID0gOSBmb3IgdGhlIHN0YXJ0aW5nIG1lYWwgMi48YnIgXC8+XHJcbmsgPSAyOiBNaXJrbyBwYXlzIEExID0gMTAgZm9yIHRoZSBzdGFydGluZyBtZWFsIDEsIHRoZW4gQjIgPSAzIGZvciBtZWFsIDIuPGJyIFwvPlxyXG5rID0gMzogTWlya28gcGF5cyBBMSA9IDEwIGZvciB0aGUgc3RhcnRpbmcgbWVhbCAxLCB0aGVuIEIyID0gMyBmb3IgbWVhbCAyLCBhbmQgZmluYWxseSBCMz0gNSBmb3IgbWVhbCAzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d