사각 사각
시간 제한1초메모리 제한128 MB
직사각형들을 일렬로 놓을 때 각 직사각형의 방향(가로/세로)을 선택해 바닥면과 양 끝 수직면을 제외한 윗부분 둘레의 총합을 최대화하는 문제입니다.
문제
n개의 사각형이 주어진다. 사각형에는 1부터 n까지 번호가 매겨져 있다. 이 사각형들을 번호 순서대로 왼쪽에서 오른쪽으로 빈틈없이 맞붙여 x축 위에 놓는다. 각 사각형은 짧은 변 또는 긴 변이 바닥(x축)에 닿도록 세울 수 있다.
이때 도형 전체의 '위쪽 둘레'가 가장 길어지도록 각 사각형의 방향을 정하려고 한다. 위쪽 둘레란 전체 둘레에서 x축에 닿아 있는 바닥 변과, 양 끝(가장 왼쪽과 가장 오른쪽)의 세로 변을 제외한 나머지 변들의 길이의 합을 말한다.
위쪽 둘레가 최대가 될 때 그 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사각형의 개수 n이 주어진다. 다음 n개의 줄에 각각 두 정수 ai와 bi가 주어지며, 이는 i번째 사각형의 두 변의 길이이다. (0 < n < 1000; 0 < ai < bi < 1000)
출력
위쪽 둘레의 최댓값을 정수로 한 줄에 출력한다.
힌트
위 그림은 어떤 예시의 사각형들을 위쪽 둘레가 최대가 되도록 배치한 모습이다. 위쪽 둘레에 포함되는 변은 DC, CG, GF, FJ, JI, IM, ML, LP, PO이며, 이들의 길이를 모두 더하면 68이 된다.