구름 놀이동산은 다양한 제한시간동안 놀이기구를 무제한으로 이용할 수 있는 자유 이용권을 판매한다. 홍현이는 이제껏 타고 싶었던 개의 놀이기구를 마음속으로 생각하며 구름 놀이동산에 방문하였다. 하지만 여지껏 이용해왔던 시간 제한이 없는 자유 이용권이 아닌 제한 시간이 있는 자유 이용권을 보고 매우 당황했다.

효율적으로 돈을 사용하고 싶어하는 홍현이를 위해, 놀이기구 사이의 이동 시간이 주어졌을 때, 모든 놀이기구를 한번씩만 방문하기 위해 걸리는 최소 시간을 구해보자.

입력

첫 번째 줄에는 놀이기구의 개수 이 주어진다. 

두 번째 줄부터 놀이기구를 이동하는데 필요한 시간이 주어진다. 는 번 놀이기구에서 번 놀이기구로 이동하는데 필요한 시간을 뜻한다.  

이때 인 경우, 번 놀이기구에서 번 놀이기구로 이동할 수 없음을 뜻한다.

출력

모든 놀이기구를 한번씩만 방문하고 처음 시작점으로 돌아오기 위해 필요한 최소 시간을 출력한다.