속초로 워크샵을 떠난 N명의 선생님들은 설악산을 등산하기로 하였다.

i번째 선생님은 산을 올라가는 데 U(i)만큼의 시간이, 내려가는 데 D(i)만큼의 시간이 걸린다.

등산 초보인 선생님들을 위하여 산신령 A는 올라가는 선생님들을 봐 주고, 산신령 B는 내려가는 선생님들을 봐 주기로 하였다.

모든 선생님이 도움을 받아야 하고, 각 방향에는 한 명의 산신령만이 있기 때문에, 어느 시점에서도 산신령 A의 도움을 받는 최대 한 명의 선생님만 산을 올라갈 수 있으며, 마찬가지로 산신령 B의 도움을 받는 최대 한 명의 선생님만 산을 내려갈 수 있다.

산을 올라왔지만 내려가기를 기다리는 선생님들이 산 꼭대기에 다수 있을 수 있고, 선생님들은 올라온 순서와 다른 순서로 내려갈 수 있다.

N명의 선생님들이 모두 등산을 끝마치는데 걸리는 최소 시간을 구하여라.

등산 (Mountain Climbing) timer 1s memory 128MB

등산 (Mountain Climbing) 1s 128MB