시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 7 7 77.778%

문제

n 개의 사각형이 주어진다. 사각형에는 1 부터 n 까지 번호가 주어진다. 아람이는 x축 위에 이것들을 번호 순서대로 왼쪽에서 오른쪽으로 밀착시켜서 붙이려고한다. 그림에서 보이듯이 각 사각형은 짧은 변 혹은 긴 변이 바닥에 붙도록 놓여진다. 아람이는 이 사각형의 위쪽의 둘레가 가장 긴 경우가 되도록 사각형을 놓으려고 한다. 위쪽의 둘레라는 것은 x축과 붙어있는 바닥과 양옆 사이드 변의 길이를 제외 한 것을 말한다.

사각형들의 위쪽 둘레가 가장 길어지는 경우의 위쪽 둘레의 길이를 계산하는 프로그램을 작성하시오.

입력

첫 번째 줄부터 표준입력으로 들어온다. 첫 번째 줄에는 사각형의 개수 n이 주어진다. 다음 줄부터 n개의 줄에 ai 와 bi가 주어진다. ai와 bi는 사각형의 두 변의 길이이다. (0 < n < 1000; 0 < ai < bi < 1000)

출력

양수 정수로 최대 위쪽 둘레를 출력한다.

예제 입력 1

5
2 5
3 8
1 10
7 14
2 5

예제 출력 1

68

힌트

위의 그림은 주어진 예제의 사각형을 위쪽 둘레가 최댓값이 되도록 배치한 모습이다.

위쪽 둘레가 포함하는 변은 DC, CG, GF, FJ, JI, IM, ML, LP, PO 이다. 그래서 총 길이의 합은 68이 된다.

W3sicHJvYmxlbV9pZCI6IjMzNTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYWNcdWFjMDEgXHVjMGFjXHVhYzAxIiwiZGVzY3JpcHRpb24iOiI8cD5uIFx1YWMxY1x1Yzc1OCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM1ZDBcdWIyOTQgMSBcdWJkODBcdWQxMzAgbiBcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDtcdWM1NDRcdWI3OGNcdWM3NzRcdWIyOTQgeFx1Y2Q5NSBcdWM3MDRcdWM1ZDAgXHVjNzc0XHVhYzgzXHViNGU0XHVjNzQ0IFx1YmM4OFx1ZDYzOCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWJjMDBcdWNjMjlcdWMyZGNcdWNmMWNcdWMxMWMgXHViZDk5XHVjNzc0XHViODI0XHVhY2UwXHVkNTVjXHViMmU0LiZuYnNwO1x1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWJjZjRcdWM3NzRcdWI0ZWZcdWM3NzQgXHVhYzAxIFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM5ZTdcdWM3NDAgXHViY2MwIFx1ZDYzOVx1Yzc0MCBcdWFlMzQgXHViY2MwXHVjNzc0IFx1YmMxNFx1YjJlNVx1YzVkMCBcdWJkOTlcdWIzYzRcdWI4NWQgXHViMTkzXHVjNWVjXHVjOWM0XHViMmU0LiBcdWM1NDRcdWI3OGNcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM3MDRcdWNhYmRcdWM3NTggXHViNDU4XHViODA4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViMTkzXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWM3MDRcdWNhYmRcdWM3NTggXHViNDU4XHViODA4XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0MCB4XHVjZDk1XHVhY2ZjIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWJjMTRcdWIyZTVcdWFjZmMgXHVjNTkxXHVjNjA2IFx1YzBhY1x1Yzc3NFx1YjRkYyBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHViOTdjIFx1YzgxY1x1YzY3OCBcdWQ1NWMgXHVhYzgzXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHVhYzAxXHVkNjE1XHViNGU0XHVjNzU4IFx1YzcwNFx1Y2FiZCBcdWI0NThcdWI4MDhcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YWUzOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTgmbmJzcDtcdWM3MDRcdWNhYmQgXHViNDU4XHViODA4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAmbmJzcDthaSBcdWM2NDAmbmJzcDtiaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIGFpXHVjNjQwJm5ic3A7YmlcdWIyOTQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjQ1MCBcdWJjYzBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LiAoMCAmbHQ7IG4gJmx0OyAxMDAwOyAwICZsdDsgYWkmbmJzcDsmbHQ7IGJpJm5ic3A7Jmx0OyAxMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzU5MVx1YzIxOCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjZDVjXHViMzAwIFx1YzcwNFx1Y2FiZCBcdWI0NThcdWI4MDhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMzM1OVwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNTVweDsgd2lkdGg6NDY1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNjA4XHVjODFjXHVjNzU4Jm5ic3A7XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0Jm5ic3A7XHVjNzA0XHVjYWJkIFx1YjQ1OFx1YjgwOFx1YWMwMCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NzQgXHViNDE4XHViM2M0XHViODVkIFx1YmMzMFx1Y2U1OFx1ZDU1YyBcdWJhYThcdWMyYjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Y2FiZCBcdWI0NThcdWI4MDhcdWFjMDAgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YmNjMFx1Yzc0MCZuYnNwO0RDLCBDRywgR0YsIEZKLCBKSSwgSU0sIE1MLCBMUCwmbmJzcDtQTyBcdWM3NzRcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWNkMWQgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0MCA2OFx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMzNTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZWN0YW5nbGVzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhcmUgbiByZWN0YW5nbGVzLCBudW1iZXJlZCBmcm9tIDEgdG8gbi4gV2UgcGxhY2UgdGhlbSB0aWdodGx5IG9uIHRoZSBheGlzIE9YLCBmcm9tIGxlZnQgdG8gcmlnaHQsIGFjY29yZGluZyB0byByZWN0YW5nbGVzJnJzcXVvOyBudW1iZXJzLiBFYWNoIHJlY3RhbmdsZSBzdGF5cyBvbiB0aGUgYXhpcyBPWCBlaXRoZXIgYnkgaXRzIHNob3J0ZXIgb3IgYnkgaXRzIGxvbmdlciBzaWRlIChzZWUgdGhlIHBpY3R1cmUgYmVsb3cpLiBDb21wdXRlIHRoZSBsZW5ndGggb2YgdGhlIHVwcGVyIGVudmVsb3AgbGluZSwgaS5lLiBwZXJpbWV0ZXImcnNxdW87cyBsZW5ndGggb2YgdGhlIG9idGFpbmVkIGZpZ3VyZSBtaW51cyB0aGUgbGVuZ3RoIG9mIHRoZSBsZWZ0LCByaWdodCBhbmQgYm90dG9tIHN0cmFpZ2h0IGxpbmUgc2VnbWVudHMgb2YgdGhlIHBpY3R1cmUuIFdyaXRlIHByb2dyYW0gcmVjIHRvIGZpbmQgdGhlIG1heGltdW0gcG9zc2libGUgbGVuZ3RoIG9mIHRoZSB1cHBlciBlbnZlbG9wIGxpbmUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQsIHRoZSB2YWx1ZSBvZiBuIGlzIHdyaXR0ZW4uIE9uIGVhY2ggb2YgdGhlIG5leHQgbiBsaW5lcywgdHdvIGludGVnZXJzIGFyZSBnaXZlbiAmbmRhc2g7IGE8c3ViPmk8XC9zdWI+IGFuZCBiPHN1Yj5pPFwvc3ViPiAmbmRhc2g7IHRoZSBzaWRlIGxlbmd0aHMgb2YgdGhlIGl0aCByZWN0YW5nbGUuICgwICZsdDsgbiAmbHQ7IDEwMDA7IDAgJmx0OyBhPHN1Yj5pPFwvc3ViPiAmbHQ7IGI8c3ViPmk8XC9zdWI+ICZsdDsgMTAwMCwgZm9yIGVhY2ggaSA9IDEsIDIsICZoZWxsaXA7LCBuLik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiBhIGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCwgeW91ciBwcm9ncmFtIHNob3VsZCB3cml0ZSB0aGUgcmVzdWx0IGFzIGEgcG9zaXRpdmUgaW50ZWdlci48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMzM1OVwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNTVweDsgd2lkdGg6NDY1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSBjb25maWd1cmF0aW9uLCB0aGF0IHlpZWxkcyB0aGUgbWF4aW11bSBsZW5ndGggb2YgdGhlIHVwcGVyIGVudmVsb3AgbGluZSwgaXMgcHJlc2VudGVkIG9uIHRoZSBwaWN0dXJlLjxcL3A+XHJcblxyXG48cD5UaGUgdXBwZXIgZW52ZWxvcCBsaW5lIGNvbnNpc3RzIG9mIHNlZ21lbnRzIERDLCBDRywgR0YsIEZKLCBKSSwgSU0sIE1MLCBMUCwgYW5kIFBPLiBUaGUgdG90YWwgbGVuZ3RoIGlzIDUgKyA2ICsgMyArIDcgKyAxMCArIDEzICsgNyArIDEyICsgNSA9IDY4LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Junior Balkan Olympiad in Informatics > JBOI 2008 3번