긴급 대피

일본 정부는 2020년에 외국인 관광객 수를 4천만 명으로, 2030년에는 6천만 명으로 늘릴 계획이다. 이런 목표를 달성하려면 관광 매력을 높이는 것뿐만 아니라 관광 인프라를 더 개발하는 것도 필수적이다.

수송 개선 방안 중 하나는 한 번에 많은 승객을 태울 수 있도록 매우 길거나 넓은 차량을 제공하는 것이다. 그러나 차량이 너무 크면 비상시 모든 승객을 대피시키는 데 시간이 너무 오래 걸릴 수 있다. 이 시간을 추정하는 일을 도와달라는 요청을 받았다.

차량의 좌석 배치는 다음과 같다고 가정한다.

• 중앙 통로가 차량을 곧게 관통하며, 차량 뒤쪽 중앙의 비상구 문과 바로 연결된다.
• 같은 수의 승객 좌석이 통로 양쪽에 줄지어 있다.

요청된 대략적인 추정은 단순한 단계별 모델을 바탕으로 한다. 모든 승객은 처음에 서로 다른 좌석에 앉아 있으며, 각 단계에서 다음 행동 중 하나를 할 수 있다.

• 좌석에 있는 승객은 통로 쪽으로 인접한 좌석으로 이동할 수 있다. 통로에 인접한 좌석에 있는 승객은 옆으로 곧장 통로로 이동할 수 있다.
• 통로에 있는 승객은 좌석 한 줄만큼 뒤로 이동할 수 있다. 비상구 앞, 즉 가장 뒤쪽 좌석 줄 옆에 있는 승객은 차량에서 내릴 수 있다.

이동하려는 좌석이나 통로 위치는 비어 있어야 한다. 단계가 시작되기 전에 다른 승객이 그곳에 없거나, 그곳에 있는 승객이 같은 단계에서 다른 위치로 이동해 자리를 비운 경우여야 한다. 두 명 이상의 승객이 같은 위치로 이동할 조건을 만족하면 그중 한 명만 이동할 수 있고, 나머지는 원래 위치에서 기다린다.

그림 C.1의 가장 왼쪽 그림은 예제 입력 1에 나온 작은 차량의 좌석 배치를 나타낸다. 차량에는 좌석이 다섯 줄 있고 통로 양쪽에 두 개씩, 모두 스무 개가 있다. 탑승한 승객 일곱 명의 초기 위치도 함께 표시되어 있다.

그림 C.1의 나머지 두 그림은 첫 번째와 두 번째 단계가 끝난 뒤 승객이 있을 수 있는 위치를 나타낸다. 승객의 이동은 굵은 화살표로 표시되어 있다. 앞줄에 있던 승객 두 명은 첫 단계에서 빈자리를 기다려야 했고, 둘째 줄에 있던 승객 한 명은 다음 단계에서 기다려야 했다.

여러분의 과제는 좌석 배치와 승객의 초기 위치가 주어졌을 때, 모든 승객이 차량에서 내리는 데 필요한 최소 단계 수를 구하는 프로그램을 작성하는 것이다.

그림 C.1. 단순 모델

입력은 다음 형식의 단일 테스트 케이스로 이루어진다.

r s p
i1 j1
.
.
.
ip jp

여기서 r은 승객 좌석 줄 수, s는 통로 양쪽에 있는 좌석 수, p는 승객 수이다. 이들은 1 ≤ r ≤ 500, 1 ≤ s ≤ 500, 1 ≤ p ≤ 2rs를 만족하는 정수이다.

다음 p개 줄은 승객의 초기 좌석 위치를 나타낸다. ik와 jk가 주어지는 k번째 줄은 k번째 승객의 좌석이 ik번째 좌석 줄에 있고 그 줄에서 jk번째 좌석임을 뜻한다. 줄과 좌석은 각각 앞에서 뒤로, 왼쪽에서 오른쪽으로 1부터 센다. 이들은 1 ≤ ik ≤ r, 1 ≤ jk ≤ 2s를 만족한다. 승객은 서로 다른 좌석에 앉아 있다. 즉 k ≠ l이면 ik ≠ il 또는 jk ≠ jl이다.

모든 승객이 차량에서 내리는 데 필요한 최소 단계 수를 나타내는 정수 하나를 한 줄에 출력한다.