Jumping King

Time limit2sMemory limit1024 MB

Summary

Given a grid of jump directions and distances, change at most K cells to find the minimum and maximum number of escapable cells.

Level: Medium7 of 10
Topics: Graph, BFS, Greedy
Solved: No attempts yet

Problem

Jumping King is a superhuman with enormous jumping power. One day, while traveling the world by jumping, he landed badly and got trapped in a jump prison. The jump prison is a grid with $N$ rows and $M$ columns, and from each cell you can only jump in the given direction and distance. If you can escape the prison by starting a jump from a certain cell, that cell is called an escapable cell. Escaping the prison means that the result of a jump lands outside the grid.

In the jump prison above, the cell at (2, 2) marked R2 is an escapable cell, and no other cell is escapable.

Input

The first line contains the grid size $N$ , $M$ and the number of cells $K$ that you can modify, separated by spaces. $(1 \leq N, M \leq 1\,000;\ 0 \leq K \leq NM)$

The next $N$ lines each contain $M$ characters $D_{ij}$ , separated by spaces, giving the jump direction of each cell. Each character is one of L, R, U, D.

The next $N$ lines each contain $M$ integers $L_{ij}$ , separated by spaces, giving the jump distance of each cell. $(0 \leq L_{ij} \leq 1\,000)$

Output

Print the minimum and the maximum number of escapable cells that can be achieved by modifying at most $K$ cells, separated by a space.

Examples2

Example 1

Input

3 3 2
R R D
U R D
U U L
1 1 1
0 2 1
1 2 1

Expected output

0 9

Example 2
Input
```
2 3 1
R L U
R D D
1 1 0
1 2 3
```
Expected output
```
1 5
```