시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 74 13 12 27.907%

문제

화산학자 윤재상은 어느 화산섬을 탐사하러 갔다가 곧 섬에 있는 화산들이 곧 폭발하기 시작할 것이라는 급보와 각 화산의 폭발 시점 정보를 받았다.

섬은 M행 N열의 행렬로 표현된다. 어떤 화산의 위치를 (x, y), 폭발을 시작한 시각을 t 라고 하자. t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다. 재상인 빨리 탈출을 하고싶다.

  • 재상이는 처음에 X행 Y열에 있다.
  • 재상이는 단위 시간 당 상하좌우 한 칸만 움직일 수 있다.
  • 재상이는 화산이 있는 위치와 화산쇄설류가 뒤덮인 곳은 갈 수 없다.

재상이는 화산쇄설류를 피해서 되도록 가장 높은 곳으로 피하고 싶고, 되도록 가장 빨리 도달하기를 원한다. 재상이가 화산쇄설류를 피해서 도달할 수 있는 가장 높은 고도와, 그 고도까지 도달하는데 걸리는 최소 시간을 구한다.

입력

첫 번째 줄에 정수 M, N, V이 공백으로 구분되어 주어진다. (1 ≤ M, N ≤ 100, 1 ≤ V ≤ min(5,000, M×N))

그 다음 줄에 X, Y가 공백으로 구분되어 주어진다. (1 ≤ X ≤ M, 1 ≤ Y ≤ N)

그 다음 줄부터 M개의 줄마다 N개의 공백으로 구분된 수들이 주어진다. i행 j열의 값은 (i, j) 지대의 고도 hij 를 나타낸다. (0 ≤ hij ≤ 10,000)

그 다음 줄부터 V개의 줄이 주어진다. i번째 줄에 xi, yi, ti가 공백으로 구분되어 주어진다. 이 수들은 i번째 화산의 위치 (xi, yi,)와 화산의 분출시각 ti를 의미한다. (1 ≤ xi ≤ M, 1 ≤ yi ≤ N, 0 ≤ ti ≤ 200)

위치, 시간, 고도 수치들은 모두 정수이다. X행 Y열에 화산이 있는 입력은 주어지지 않는다.

출력

재상이가 도달할 수 있는 최고 높이와 그 높이에 도달할 수 있는 최단 시간을 공백을 구분하여 출력한다.

예제 입력 1

8 8 8
5 8
58 34 30 23 12 44 18 30
4 62 26 42 64 39 44 25
64 34 6 10 0 25 46 34
42 3 62 48 20 25 25 41
35 30 4 33 35 39 41 38
7 43 37 3 0 25 20 23
20 59 18 43 1 14 16 11
17 50 12 19 59 48 7 4
4 5 4
2 6 4
5 1 2
8 8 3
5 6 2
8 2 2
5 2 1
3 5 2

예제 출력 1

46 3

예제 입력 2

8 8 8
1 8
7 9 1 60 5 49 19 27
38 25 18 1 52 43 22 0
20 35 39 43 10 17 34 43
21 50 13 34 64 57 24 48
64 18 14 40 62 11 3 58
64 22 60 15 5 16 59 8
1 61 19 9 13 53 50 14
5 30 7 13 44 25 15 63
2 3 2
2 7 2
4 6 2
2 8 2
5 8 2
4 7 2
5 2 5
6 3 1

예제 출력 2

49 2