26656번 - 점프킹

문제

점프킹은 엄청난 점프력을 가진 초인이다. 어느 날, 점프로 세계를 여행하던 점프킹은 착지를 잘못해 점프 감옥에 갇히게 되었다. 점프 감옥은 $N$행 $M$열의 격자이며, 각 칸에서는 주어진 방향과 거리로만 점프할 수 있다. 만약 점프 감옥의 특정 칸에서 점프를 시작한다면 점프 감옥을 탈출할 수 있다. 이러한 칸을 탈출 가능 칸이라 하자. 감옥을 탈출한다는 것은 점프의 결과가 격자 밖인 경우를 말한다.

예를 들어, 위와 같은 점프 감옥에서 R2가 적힌 (2, 2)칸은 탈출 가능 칸이며 다른 칸들은 탈출 가능 칸이 아니다.

점프킹의 동료인 당신은 점프킹을 위해 최대 $K$개의 칸을 조작해 점프 거리를 원하는 값으로 바꿀 수 있다. 적힌 칸과 반대 방향으로 점프할 수는 없기 때문에 바꾼 점프 거리 역시 음이 아닌 정수여야 한다. 최대 $K$개의 칸을 조작해 만들 수 있는 탈출 가능 칸 개수의 최솟값과 최댓값을 구하여라.

입력

첫 번째 줄에 격자의 크기 $N,ドル $M$과 조작 가능한 칸의 개수 $K$가 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 1,000円;$ 0ドル \leq K \leq NM)$

다음 $N$개의 줄에 각 칸의 점프 방향을 나타내는 $M$개의 문자 $D_{ij}$가 L, R, U, D 중 하나로 공백으로 구분되어 주어진다.

다음 $N$개의 줄에 각 칸의 점프 거리를 나타내는 $M$개의 정수 $L_{ij}$가 공백으로 구분되어 주어진다. $(0 \leq L_{ij} \leq 1,000円)$

출력

최대 $K$개의 칸을 조작해 만들 수 있는 탈출 가능 칸 개수의 최솟값과 최댓값을 공백으로 구분해 출력한다.

제한

힌트