Exploding Robot

While Luca was looking through old boxes in his attic, he found its old nokia phone, still working! So he decides to play his favorite game on it: Exploding Robot.

The main character of the game is a robot, that starts at the top-left corner of a grid with $N$ rows and $M$ columns, and moves according to a given sequence of commands, each indicating a step to the right, down, left or up. The robot never leaves the grid. The game forces you to place $K$ bombs in distinct cells of the grid (but not on the starting cell) before the robot starts moving.

When the robot visits a cell containing a bomb, it explodes and the game ends. You like to watch the robot move, so you want to place the bombs in such a way that allows the robot to make as many moves as possible before it explodes (or he runs out of moves).

Task

What is the maximum number of moves the robot can make, if you place the bombs optimally? Note that the move that makes the robot step on a bomb is not counted.

Input data

The input file consists of:

• a line containing integers $N$, $M$ and $K$, the dimensions of the grid and the number of bombs you must place.
• a line containing string $P$, the list of moves the robot will make.

Output data

The output file must contain a single line consisting of integer $\mathtt{ans}$.

Constraints and clarifications

• $2 \le N \le 100, 2 \le M \le 100$.
• $0 \le K < N \cdot M$.
• $1 \le |P| \le 5 \ 000$.
• $P$ contains only characters $\text{R}$, $\text{D}$, $\text{L}$ and $\text{U}$, indicating a step right, down, left or up.
• The robot never leaves the grid while executing the moves in $P$.

Example 1

stdin

2 2 2
RDL

stdout

1

Explanation

The first sample case is shown in the figure below.

The blue line shows the path of the robot. By placing the bombs like in the figure, the robot can make $1$ move before stepping on a bomb.

Example 2

stdin

5 5 2
DDDRD

stdout

5

Explanation

The second sample case is shown in the figure below.

The figure shows a possible placement of the bombs that allows the robot to make $5$ moves.

Example 3

stdin

3 4 7
RDDRLUURRDDLUU

stdout

7