https://www.acmicpc.net/board/...

견우와 직녀는 여러 개의 섬과 절벽으로 이루어진 장소에 살고 있다. 평상시에는 절벽을 건너지 못 하기 때문에 서로 만날 수가 없다. 하지만 7월 7일은 특별한 날이다. 이 날에는 까마귀와 까치가 서로 힘을 합쳐 다리를 만들어, 견우와 직녀가 절벽을 건너 서로 만날 수 있기 때문이다.

최근에 까마귀와 까치에게 문제가 생겼다. 급속도로 진행된 고령화로 인해서 견우와 직녀가 한 번에 만날 수 있을 만큼 커다란 오작교를 만들 수 없다. 요즘에는 견우와 직녀가 만날 수 있도록 최소한의 절벽에만 다리를 만들어 주고 있었다. 까마귀와 까치는 이마저도 힘들어했기 때문에, 1분간 오작교를 만들면 몇 분 동안은 꼭 쉬는 시간을 가져야 했다.

예를 들어 오작교가 3분과 4분 주기라면, 건널 수 있는 시간은 아래 그림에서 초록색으로 표시한 부분과 같다. 흰색으로 표시한 시간에는 오작교를 건널 수 없다.

[그림 1]

또한, 견우는 안전을 위해 두 번 연속으로 오작교를 건너지는 않기로 했다.

까마귀와 까치는 조금이라도 견우를 더 도와주기 위해 절벽을 하나 골라 주기가 M분인 오작교를 하나 더 놓아 주기로 했다. 단, 이미 오작교를 짓기로 예정한 절벽에는 오작교를 하나 더 놓을 수 없고, 아래와 같이 절벽이 가로와 세로로 교차하는 곳에도 오작교를 놓을 수 없다. 아래 그림에서 파란색은 견우가 건널 수 있는 일반적인 땅, 검은색은 절벽, 흰색은 절벽이 교차해서 오작교를 놓을 수 없는 위치를 나타낸다.

[그림 2]

견우는 짧은 만남이 이런 악조건에서 더욱 짧아지는 것을 원하지 않았다. 견우가 직녀에게 도착할 수 있는 최소의 시간을 찾아라.

추가 요청 1: 입력 설명에서 "이 문제에서"를 빼 주세요.

추가 요청 2: https://www.acmicpc.net/board/... 데이터 추가 건의가 있었습니다. 적어도 한 절벽에 오작교를 추가로 놓을 수 있음이 보장되면 입력 설명에서 명시해 주시고, 보장되지 않으면 이 글의 "하나 더 놓아 주기로 했다." 뒤에 "(오작교를 놓지 않을 수도 있다.)"를 추가해 주세요.