25607번 - Shooting Game

현재 우주에서 지구로 많은 수의 운석이 떨어지고 있다. 한국항공대학교에도 역시 많은 운석이 떨어지고 있다. 항공대 마스코트 마하는 이를 두고 볼 수 없어 항공대의 A300-600 비행기를 타고 운석을 직접 파괴하려고 한다.

한국항공대학교의 상공은 $N \times N$ 크기의 격자칸으로 표현되고, 각 칸은 운석, 비행기, 빈 칸 중 하나이다.

• 운석: 운석은 총 $K$개가 주어진다. 운석은 1초에 한 칸씩 위에서 아래로 한 칸 떨어진다. 또한 모든 운석의 열 번호는 서로 다르다.
• 비행기: 항공대의 A300-600 비행기가 처음에 위치 하고 있는 칸이다. 비행기는 $N$행 $C$열에 존재한다.
  • 비행기는 1초에 세 가지 동작 중 하나를 진행 할 수 있다.
    • 왼쪽으로 이동
    • 오른쪽으로 이동
    • 미사일 발사해 비행기와 같은 열의 운석 제거
• 빈 칸: 언제나 운석과 비행기가 이동할 수 있다.

마하는 다음과 같은 과정으로 운석을 제거한다.

1. 비행기가 3가지 동작 중 하나를 진행한다.
2. 운석이 1초 동안 한 칸 아래로 떨어진다.
3. 만약 운석 중 하나라도 비행기와 같은 행의 위치에 있게 된다면 -1을 출력한다. 아니면 1번부터 다시 반복한다.

이때 항공대 마스코트 마하가 운석을 다 파괴해 항공대를 무사히 지킬 수 있는 최소 시간을 출력하시오. 만약 운석을 다 파괴하지 못하고 운석의 위치가 비행기와 같은 행의 위치에 도달 할 경우 -1을 출력하시오.

첫째 줄에 $N$, $K$가 주어진다. ($5 \le N \le 100$, $1 \le K \le 15$)

둘째 줄부터 $K$개 줄에 운석의 위치가 행($r$), 열($c$) ($1 \le r < N$, $1 \le c \le N$)로 주어진다. (단, 하나의 운석이 다른 운석과 동일한 열을 가질 수 없다.)

마지막 줄에 현재 비행기의 위치 열($C$)이 주어진다. ($1 \le C \le N$)

마하가 모든 운석을 파괴할 수 있는 최소 시간을 출력한다. 만약 항공대를 지킬 수 없다면 -1을 출력한다.