시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 512 MB 117 41 32 30.189%

문제

전성기 시절의 오버워치는 지구 상에서 가장 진보된 최첨단 무기를 보유했으며, 그 무기의 출처는 바로 토르비욘 린드홀름이라는 전무후무한 기술자의 작업장이었다.

하지만 이런 토르비욘에게도 진상손님이 있었으니....

진상 손님 한조는 만우절을 기념해 동생인 겐지에게 이상한 검을 선물하겠다며 토르비욘에게 말도 안되는 주문을 했다.

토르비욘이 받은 괴상한 주문은 아래와 같다.

직사각형 모양의 철판을 한 줄로 용접해서 만들며 절대 자르지 않을 것.

명색이 검이므로 철판을 이을 때는 너비가 점점 줄어들어야 한다. 너비가 더 커지거나 같은 길이로도 이어 붙일 수 없다.

검은 가장 길게 만들어야 할 것.

다행히도 토르비욘이 가진 모든 철판들을 이용해서 한조가 원하는 검을 만들 수 있다. 토르비욘은 실물을 만들기 전에 견적을 내보려고 한다. 세상에서 가장 긴 검을 만들기 전에 검을 건조시킬 높은 작업장을 먼저 지어야 하기 때문이다.

검의 길이를 구하여라.

입력

첫번째 줄에는 철판의 갯수인 정수 n이 입력된다. (1 ≤ n ≤ 250 000)

이후 입력되는 n개의 줄에는 철판의 길이인 s와 t가 입력된다. (1 ≤ s ≤ t ≤ 109 nm)

 

출력

n개의 철판을 모두 사용해 만들 수 있는 가장 긴 검의 길이를 구하여라. 검의 너비는 반드시 줄어들어야 한다.

예제 입력 1

3
50000 160000
50000 100000
50000 100000

예제 출력 1

200000
W3sicHJvYmxlbV9pZCI6IjEzMzYxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjZDVjXHVhY2UwXHVjNzc4IFx1YjMwMFx1YzdhNVx1YzdhNVx1Yzc3NCBcdWQxYTBcdWI5NzRcdWJlNDRcdWM2OTgiLCJkZXNjcmlwdGlvbiI6IjxwPjxlbT5cdWM4MDRcdWMxMzFcdWFlMzAgXHVjMmRjXHVjODA4XHVjNzU4IFx1YzYyNFx1YmM4NFx1YzZjY1x1Y2U1OFx1YjI5NCBcdWM5YzBcdWFkNmMgXHVjMGMxXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5YzRcdWJjZjRcdWI0MWMgXHVjZDVjXHVjY2E4XHViMmU4IFx1YmIzNFx1YWUzMFx1Yjk3YyBcdWJjZjRcdWM3MjBcdWQ1ODhcdWM3M2NcdWJhNzAsIFx1YWRmOCBcdWJiMzRcdWFlMzBcdWM3NTggXHVjZDljXHVjYzk4XHViMjk0IFx1YmMxNFx1Yjg1YyBcdWQxYTBcdWI5NzRcdWJlNDRcdWM2OTggXHViOWIwXHViNGRjXHVkNjQwXHViOTg0XHVjNzc0XHViNzdjXHViMjk0IFx1YzgwNFx1YmIzNFx1ZDZjNFx1YmIzNFx1ZDU1YyBcdWFlMzBcdWMyMjBcdWM3OTBcdWM3NTggXHVjNzkxXHVjNWM1XHVjN2E1XHVjNzc0XHVjNWM4XHViMmU0LjxcL2VtPjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzc0XHViN2YwIFx1ZDFhMFx1Yjk3NFx1YmU0NFx1YzY5OFx1YzVkMFx1YWM4Y1x1YjNjNCBcdWM5YzRcdWMwYzFcdWMxOTBcdWIyZDhcdWM3NzQgXHVjNzg4XHVjNWM4XHVjNzNjXHViMmM4Li4uLjxcL3A+XHJcblxyXG48cD5cdWM5YzRcdWMwYzEgXHVjMTkwXHViMmQ4IFx1ZDU1Y1x1Yzg3MFx1YjI5NCBcdWI5Y2NcdWM2YjBcdWM4MDhcdWM3NDQgXHVhZTMwXHViMTUwXHVkNTc0IFx1YjNkOVx1YzBkZFx1Yzc3OCBcdWFjOTBcdWM5YzBcdWM1ZDBcdWFjOGMgXHVjNzc0XHVjMGMxXHVkNTVjIFx1YWM4MFx1Yzc0NCBcdWMxMjBcdWJiM2NcdWQ1NThcdWFjYTBcdWIyZTRcdWJhNzAgXHVkMWEwXHViOTc0XHViZTQ0XHVjNjk4XHVjNWQwXHVhYzhjIFx1YjlkMFx1YjNjNCBcdWM1NDhcdWI0MThcdWIyOTQgXHVjOGZjXHViYjM4XHVjNzQ0IFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMWEwXHViOTc0XHViZTQ0XHVjNjk4XHVjNzc0IFx1YmMxYlx1Yzc0MCBcdWFkMzRcdWMwYzFcdWQ1NWMgXHVjOGZjXHViYjM4XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxlbT5cdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzU4IFx1Y2NhMFx1ZDMxMFx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YzZhOVx1YzgxMVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTRcdWJhNzAgXHVjODA4XHViMzAwIFx1Yzc5MFx1Yjk3NFx1YzljMCBcdWM1NGFcdWM3NDQgXHVhYzgzPFwvZW0+LjxcL3A+XHJcblxyXG48cD48ZW0+XHViYTg1XHVjMGM5XHVjNzc0IFx1YWM4MFx1Yzc3NFx1YmJjMFx1Yjg1YyBcdWNjYTBcdWQzMTBcdWM3NDQgXHVjNzc0XHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWIxMDhcdWJlNDRcdWFjMDAgXHVjODEwXHVjODEwIFx1YzkwNFx1YzViNFx1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjEwOFx1YmU0NFx1YWMwMCBcdWIzNTQgXHVjZWU0XHVjOWMwXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWFlMzhcdWM3NzRcdWI4NWNcdWIzYzQgXHVjNzc0XHVjNWI0IFx1YmQ5OVx1Yzc3YyBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2VtPjxcL3A+XHJcblxyXG48cD48ZW0+XHVhYzgwXHVjNzQwIFx1YWMwMFx1YzdhNSBcdWFlMzhcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU2MCBcdWFjODMuPFwvZW0+PFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1ZDU4OVx1ZDc4OFx1YjNjNCBcdWQxYTBcdWI5NzRcdWJlNDRcdWM2OThcdWM3NzQgXHVhYzAwXHVjOWM0IFx1YmFhOFx1YjRlMCBcdWNjYTBcdWQzMTBcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDU1Y1x1Yzg3MFx1YWMwMCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVhYzgwXHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQxYTBcdWI5NzRcdWJlNDRcdWM2OThcdWM3NDAgXHVjMmU0XHViYjNjXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVhY2FjXHVjODAxXHVjNzQ0IFx1YjBiNFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzEzOFx1YzBjMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWM4MFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjODA0XHVjNWQwIFx1YWM4MFx1Yzc0NCBcdWFjNzRcdWM4NzBcdWMyZGNcdWQwYWMgXHViMTkyXHVjNzQwIFx1Yzc5MVx1YzVjNVx1YzdhNVx1Yzc0NCBcdWJhM2NcdWM4MDAgXHVjOWMwXHVjNWI0XHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4MFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjYTBcdWQzMTBcdWM3NTggXHVhYzJmXHVjMjE4XHVjNzc4IFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4mbmJzcDsoMSAmbGU7IG4gJmxlOyAyNTAgMDAwKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgXHVjNzg1XHViODI1XHViNDE4XHViMjk0IG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NhMFx1ZDMxMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3Nzggc1x1YzY0MCB0XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4mbmJzcDsoMSAmbGU7IHMgJmxlOyB0ICZsZTsgMTA8c3VwPjk8XC9zdXA+Jm5ic3A7bm0pPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPm5cdWFjMWNcdWM3NTggXHVjY2EwXHVkMzEwXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWFjODBcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy4gXHVhYzgwXHVjNzU4IFx1YjEwOFx1YmU0NFx1YjI5NCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjOTA0XHVjNWI0XHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMzM2MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhpZ2hlc3QgVG93ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPk9uaSBsb3ZlZCB0byBidWlsZCB0YWxsIHRvd2VycyBvZiBibG9ja3MuIEhlciBwYXJlbnRzJm5ic3A7d2VyZSBub3QgYXMgYW11c2VkIHRob3VnaC4gVGhleSB3ZXJlIG9uIHRoZSB2ZXJnZSZuYnNwO29mIGdvaW5nIGNyYXp5IG92ZXIgdGhhdCBhbm5veWluZyBsb3VkIG5vaXNlIHdoZW5ldmVyJm5ic3A7YSB0b3dlciBmZWxsIHRvIHRoZSBncm91bmQsIG5vdCB0byBtZW50aW9uIGhhdmluZyZuYnNwO3RvIHBpY2sgdXAgYmxvY2tzIGZyb20gdGhlIGZsb29yIGFsbCB0aGUgdGltZS4gT25pJnJzcXVvO3MmbmJzcDttb3RoZXIgb25lIGRheSBoYWQgYW4gaWRlYS4gSW5zdGVhZCBvZiBidWlsZGluZyZuYnNwO3RoZSB0b3dlciBvdXQgb2YgcGh5c2ljYWwgYmxvY2tzLCB3aHkgY291bGRuJnJzcXVvO3QgT25pJm5ic3A7Y29uc3RydWN0IGEgcGljdHVyZSBvZiBhIHRvd2VyIHVzaW5nIHR3by1kaW1lbnNpb25hbCZuYnNwO3JlY3RhbmdsZXMgdGhhdCBzaGUgbW9udGFnZWQgb24gYSBib2FyZCBvbiB0aGUgd2FsbD8mbmJzcDtPbmkmcnNxdW87cyBtb3RoZXIgY3V0IG91dCByZWN0YW5nbGVzIG9mIHZhcmlvdXMgc2l6ZXMgYW5kJm5ic3A7Y29sb3JzLCBkcmV3IGEgaG9yaXpvbnRhbCBsaW5lIHJlcHJlc2VudGluZyB0aGUgZ3JvdW5kJm5ic3A7YXQgdGhlIGJvdHRvbSBvZiB0aGUgYm9hcmQsIGFuZCBleHBsYWluZWQgdGhlIHJ1bGVzJm5ic3A7b2YgdGhlIGdhbWUgdG8gT25pOiBldmVyeSByZWN0YW5nbGUgbXVzdCBiZSBwbGFjZWQgaW1tZWRpYXRlbHkgYWJvdmUgYW5vdGhlciByZWN0YW5nbGUgb3IgdGhlJm5ic3A7Z3JvdW5kIGxpbmUuIEZvciBldmVyeSByZWN0YW5nbGUgeW91IGNhbiBjaG9vc2Ugd2hpY2ggb2YgaXRzIHR3byBvcmllbnRhdGlvbnMgdG8gdXNlLiBJLmUuLCBpZiBhJm5ic3A7cmVjdGFuZ2xlIGhhcyBzaWRlcyBvZiBsZW5ndGggcyBhbmQgdCwgeW91IGNhbiBlaXRoZXIgaGF2ZSBhIHNpZGUgb2YgbGVuZ3RoIHMgaG9yaXpvbnRhbGx5IG9yIGEgc2lkZSZuYnNwO29mIGxlbmd0aCB0IGhvcml6b250YWxseS4gWW91IG1heSBwbGFjZSBleGFjdGx5IG9uZSByZWN0YW5nbGUgaW1tZWRpYXRlbHkgYWJvdmUgYW5vdGhlciBvbmUgaWYmbmJzcDtpdHMgaG9yaXpvbnRhbCBzaWRlIGlzIHN0cmljdGx5IHNtYWxsZXIgdGhhbiB0aGUgaG9yaXpvbnRhbCBzaWRlIG9mIHRoZSByZWN0YW5nbGUgYmVuZWF0aC4gRXhhY3RseSZuYnNwO29uZSByZWN0YW5nbGUgbXVzdCBiZSBwbGFjZWQgb24gdGhlIGdyb3VuZCBsaW5lLiBOb3cgdHJ5IHRvIGJ1aWxkIGFzIHRhbGwgYSB0b3dlciBhcyBwb3NzaWJsZSE8XC9wPlxyXG5cclxuPHA+T25pJnJzcXVvO3MgbW90aGVyIHRvb2sgZXh0cmEgY2FyZSB0byBtYWtlIHN1cmUgdGhhdCBpdCB3YXMgaW5kZWVkIHBvc3NpYmxlIHRvIHVzZSBhbGwgcmVjdGFuZ2xlcyZuYnNwO2luIGEgdG93ZXIgaW4gb3JkZXIgbm90IHRvIGRpc2NvdXJhZ2UgT25pLiBCdXQgb2YgY291cnNlIE9uaSBxdWlja2x5IGxvc3QgaW50ZXJlc3QgYW55d2F5IGFuZCByZXR1cm5lZCB0byBoZXIgcGh5c2ljYWwgYmxvY2tzLiBBZnRlciBhbGwsIHdoYXQgaXMgdGhlIHBvaW50IG9mIGJ1aWxkaW5nIGEgdG93ZXIgaWYgeW91IGNhbm5vdCBmZWVsIHRoZSBzdXNwZW5zZSBiZWZvcmUgdGhlIGluZXZpdGFibGUgY29sbGFwc2U/IEhlciBmYXRoZXIgb24gdGhlIG90aGVyIGhhbmQgZ290IGludGVyZXN0ZWQgYnkgaGlzIHdpZmUmcnNxdW87cyBwdXp6bGUgYXMgaGUgcmVhbGl6ZWQgdGhpcyBpcyBub3QgYSBraWRzJnJzcXVvOyBnYW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDI1MCAwMDApLCB0aGUgbnVtYmVyIG9mIHJlY3RhbmdsZXMuIFRoZW4mbmJzcDtmb2xsb3cgbiBsaW5lcywgZWFjaCBjb250YWluaW5nIHR3byBpbnRlZ2VycyBzIGFuZCB0ICgxICZsZTsgcyAmbGU7IHQgJmxlOyAxMDxzdXA+OTxcL3N1cD4gbm0pLCB0aGUgZGltZW5zaW9ucyBvZiBhJm5ic3A7cmVjdGFuZ2xlLjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IHNhZmVseSBhc3N1bWUgdGhhdCB0aGVyZSBpcyBhIHdheSB0byBidWlsZCBhIHRvd2VyIHVzaW5nIGFsbCBuIHJlY3RhbmdsZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgaGVpZ2h0IGluIG5tIG9mIHRoZSB0YWxsZXN0IHBvc3NpYmxlIHRvd2VyIHVzaW5nIGFsbCB0aGUmbmJzcDtyZWN0YW5nbGVzIHdoaWxlIGhhdmluZyB0aGUgaG9yaXpvbnRhbCBzaWRlIGxlbmd0aHMgc3RyaWN0bHkgZGVjcmVhc2luZyBmcm9tIGJvdHRvbSB0byB0b3AuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d