25824번 - 빠른 오름차순 메시지 전달

선생님 1명과 학생 12명이 있다. 학생에게 1번부터 12번까지 번호가 부여된다. 학생들은 두 명씩 하나의 친구 집단을 이룬다. 1번 학생부터 번호순으로 두 명씩 하나의 친구 집단에 포함된다. 즉, 친구 집단 1은 {학생 1번, 학생 2번}, 친구 집단 2는 {학생 3번, 학생 4번}, ... , 친구 집단 6은 {학생 11번, 학생 12번}으로 구성된다.

선생님은 긴급 메시지를 12명 학생 모두에게 최대한 빠르게 전달하려고 한다. 선생님은 긴급 메시지를 친구 집단 1에 전달한다. 선생님으로부터 메시지를 전달받은 1번 또는 2번 학생은 같은 친구 집단에 있는 다른 친구 2번 또는 1번 학생에게 메시지를 전달한다. 메시지를 전달받은 1번 학생 또는 2번 학생은 친구 집단 2에 메시지를 전달한다. 메시지를 받은 친구는 앞에서 언급된 내용과 같은 방식으로 친구 집단 내에 다른 친구에게 메시지를 전달하고 메시지를 전달받은 친구는 친구 집단 3에 메시지를 전달한다. 친구 집단 4, 친구 집단 5, 친구 집단 6 순서대로 메시지를 전달하고 12명의 학생이 모두 메시지를 받으면 선생님의 메시지 전달이 완료된다. 선생님은 첫 번째 학생에게 메시지를 즉시 전달하기 때문에 첫 번째 학생이 메시지를 받는 데 걸리는 시간은 0으로 생각한다. 12명의 학생이 다른 친구에게 메시지를 전달하는 데 걸리는 시간이 주어지면, 친구 집단 1부터 친구 집단 6 순서대로 12명의 친구에게 메시지를 전달하는데 걸리는 최소 시간을 출력하자.

첫 번째 줄부터 열두 개의 줄에 걸쳐 메시지를 전달하는 데 걸리는 시간이 주어진다. i번째 줄의 j번째 숫자는 학생 i가 학생 j에게 메시지를 전달하는 데 걸리는 시간을 나타낸다.

첫 번째 줄에 친구 집단 1부터 친구 집단 6 순서대로 12명의 친구에게 메시지를 전달하는데 걸리는 최소 시간을 출력한다.

• 1 ≤ 친구끼리 메시지를 전달하는 데 걸리는 시간 ≤ 1,000
• 학생 i가 학생 j에게 메시지를 전달하는 데 걸리는 시간과 학생 j가 학생 i에게 메시지를 전달하는 데 걸리는 시간은 같다. (1 ≤ i, j ≤ 12, i ≠ j)
• 자기 자신에게 메시지를 전달하는 데 걸리는 시간은 0이다.