재배
시간 제한2초메모리 제한512 MB
R행 C열 격자에 풀 N개가 자라 있을 때, 매년 바람 방향을 하나씩 골라 모든 칸을 채우는 데 걸리는 최소 햇수를 구합니다.
문제
21XX년, IOI 행성의 주민들은 최근에 발견된 새 행성으로 이주할 계획이다.
새 행성에는 R개의 행과 C개의 열로 이루어진 직사각형 격자 모양의 들판이 있다. 열은 남북 방향과 평행하고, 행은 동서 방향과 평행하다. 북쪽에서 i번째, 서쪽에서 j번째에 있는 칸을 (i, j)라고 한다. 들판의 북서쪽 모서리는 (1, 1)이고, 남동쪽 모서리는 (R, C)이다. 매년 주민들은 들판에 부는 바람의 방향을 고른다. 방향은 동, 서, 남, 북 중 하나이다.
새 행성에서 농사를 짓기 위해 주민들은 들판 전체에 JOI 풀을 심으려 한다. 이주 첫해 봄에 들판의 N개 칸에는 JOI 풀이 있다.
JOI 풀은 바람을 타고 퍼진다. 매년 여름, 씨앗은 주민들이 고른 방향으로 바람에 실려 날아간다. 씨앗은 바람 방향으로 한 칸 이동해 떨어진다. 씨앗이 JOI 풀이 없는 칸에 떨어지면, 그 칸에는 다음 해 봄에 JOI 풀이 생긴다. 한 번 JOI 풀이 생긴 칸에는 이후에도 계속 JOI 풀이 남는다.
바람의 방향을 적절히 정할 때, 들판의 모든 칸에 JOI 풀이 생기기까지 걸리는 최소 연수를 구하라. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 두 정수 R, C가 공백으로 구분되어 주어진다. 들판은 R개의 행과 C개의 열로 이루어진 격자이다. 두 번째 줄에는 이주 첫해 봄에 JOI 풀이 있는 칸의 개수 N이 주어진다. 이어지는 N개의 줄 각각에는 두 정수 Si, Ei가 공백으로 구분되어 주어진다. 이는 칸 (Si, Ei)에 첫해 봄부터 JOI 풀이 있음을 뜻한다.
출력
바람의 방향을 적절히 정했을 때, 모든 칸에 JOI 풀이 생기기까지 걸리는 최소 연수를 한 줄에 출력한다.
제한
- 1 ≤ N ≤ 300.
- 1 ≤ R ≤ 1 000 000 000.
- 1 ≤ C ≤ 1 000 000 000.
- 1 ≤ Si ≤ R (1 ≤ i ≤ N).
- 1 ≤ Ei ≤ C (1 ≤ i ≤ N).
- 이주 첫해 봄에는 JOI 풀이 없는 칸이 적어도 하나 있다.
- (Si, Ei) ≠ (Sj, Ej) (1 ≤ i < j ≤ N).