Under construction

Still being built. Things may change

Pyroclastic Flow

Time limit1sMemory limit128 MB

Summary
On an M by N elevation grid with timed volcano eruptions whose flow spreads Manhattan style, find the reachable cell of highest elevation and the earliest arrival time there.
Level

Medium7 of 10

Topics
Shortest path, Heap, Graph, Implementation
Solved
No attempts yet

Problem

Volcanologist Yun Jaesang went to explore a volcanic island, and soon received an urgent notice that the volcanoes on the island would begin erupting, along with the eruption time of each volcano.

The island is represented as a matrix with M rows and N columns. Let the location of a volcano be (x, y) and the time it starts erupting be t. At time t+δ, every cell (u, v) with δ ≥ |u-x|+|v-y| is struck by pyroclastic flow, regardless of elevation. Jaesang wants to escape quickly.

  • Jaesang starts at row X, column Y.
  • Jaesang can move one cell up, down, left, or right per unit time.
  • Jaesang cannot go to a cell containing a volcano or a cell covered by pyroclastic flow.

Jaesang wants to flee to as high a place as possible while avoiding the pyroclastic flow, and to arrive as quickly as possible. Find the highest elevation Jaesang can reach while avoiding the pyroclastic flow, and the minimum time it takes to reach that elevation.

Input

The first line contains the integers M, N, and V separated by spaces. (1 ≤ M, N ≤ 100, 1 ≤ V ≤ min(5,000, M×N))

The next line contains X and Y separated by a space. (1 ≤ X ≤ M, 1 ≤ Y ≤ N)

From the next line, M lines each contain N space-separated numbers. The value at row i, column j is the elevation hij of cell (i, j). (0 ≤ hij ≤ 10,000)

From the next line, V lines follow. The i-th line contains xi, yi, ti separated by spaces. These numbers mean the location (xi, yi) of the i-th volcano and its eruption time ti. (1 ≤ xi ≤ M, 1 ≤ yi ≤ N, 0 ≤ ti ≤ 200)

All location, time, and elevation values are integers. No input places a volcano at row X, column Y.

Output

Print the highest elevation Jaesang can reach and the minimum time to reach that elevation, separated by a space.

Examples2

  1. Example 1

    Input
    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
    Expected output
    46 3

  2. Example 2

    Input
    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
    Expected output
    49 2