조선시대에는 임금님에게 상소문을 보낼 때 말을 이용하여 상소문을 전달하였고 이를 파발마라고 불렀다.

파발마들은 지방의 역에서 관리되었고 한 지방역에서 파발마를 이용하여 다른 지방역으로 상소문을 전달하면

다른 지방역에서 파발마를 이용하여 또 다른 지방역으로 상소문을 전달하는 식으로 몇 개의 지방역을 거쳐서 한양역까지 전달하는 것이다.

조선에는 전국에 N 개의 지방역이 있고 이 역들과 한양역을 모두 연결하는 N + 1 개의 도로가 원모양으로 연결되어 있다.

따라서 각 역들은 항상 2개의 역과 인접한다. 한양역이 원형의 꼭대기에 있는 것으로 가정하고

각 지방역은 한양역에서 시계방향으로 1번부터 시작하여 번호가 붙은 것으로 생각한다. 아래 그림은 N = 5인 경우의 예이다.

상소문은 하루에 인접한 역으로만 이동할 수 있으며 이동하지 않고 머물러 있는 것도 가능하다.

위의 그림처럼 어느날 역 3에 상소문이 있으면 그 다음날에는 역 2이나 역 4로 이동할 수 있으며 역 3에 머물러 있는 것도 가능하다.

한 역에 여러 개의 상소문이 함께 모여 있을 수 있으며 한 마리의 파발마로 여러 개의 상소문을 한꺼번에 이동하는 것도 가능하다.

여러분은 어떤 날 지방역들의 상태를 받게 된다. 각 지방역은 하나의 상소문을 가지고 있거나 없거나 둘 중 하나의 상태이다.

이 상소문을 한양역으로 보내야 하는데, 말 한 마리를 하루 사용하면 상소문 개수에 상관없이 1냥의 비용이 든다.

그리고 상소문마다 비용이 발생하는데 하나의 상소문이 한양역까지 이동하는데 D 일이 걸리면 D 냥의 비용이 든다.

이 때 처음이나 중간에 머무르는 날도 한양역으로 이동하는 날에 포함된다.

위의 그림의 경우 역 3에 있는 상소문을 역 2로 먼저 이동한 후에

두 상소문을 함께 역 2에서 역 1로 그리고 한양역으로 이동하는 경우의 비용을 계산해 보자.

먼저 첫날 역 3의 상소문을 역 2로 이동하기 위해 파발마 1마리를 사용하고

다음날 역 2의 상소문 2개를 역 1로 이동하기 위해 파말마 1마리를 사용한다.

3일째에는 역 1의 상소문 2개를 한양역으로 이동하기 위해 파발마 1마리를 사용한다.

결론적으로 총 3일 동안 매일 한 마리의 파발마를 사용하므로 3냥의 비용이 들고

두 개의 상소문이 한양역에 도착하는데 3일씩 걸리므로 6냥의 비용이 필요하여 총 9냥의 비용이 든다. 여러분은 지방역의 수와 각 지방역의 상태를 입력 받아서 모든 상소문을 한양역으로 전달하는 데 필요한

최소의 비용을 출력하는 프로그램을 작성하라.

말은 모든 지방역에 충분히 많이 있다고 가정한다.

파발마 timer 1초 memory 64MB

파발마 1초 64MB