405918: GYM102156 I Slippers
Description
"Who wakes up first gets the slippers", a Russian proverb says. However, in our campus it is not that easy. You not only have to come early (all slippers will be already taken otherwise), but also are to obey the strict rules of the shoe case.
The shoe case looks like an $$$n \times m$$$ grid. Each cell contains a slipper, either left or right. Initially, each slipper is rotated in one of the four directions: left, right, forwards or backwards. It is allowed to take any adjacent pair of slippers (not necessarily distinct) and rotate one of them 90$$$^\circ$$$ clockwise and another 90$$$^\circ$$$ counterclockwise. When you find a pair of slippers in natural position, you may put them on and finally go away, happy and warm.
A pair of slippers is in natural position if:
- their cells share a side;
- they face the same direction;
- if you look at the two cells along that direction, one cell is to the right and another is to the left. Also, there is a right slipper in the right cell and the left slipper in the left cell.
Assuming everyone is altruistic and performs in an optimal way, find the maximum number of people that can walk away with their pair of slippers put on.
InputIn the first line of input, there are two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 100$$$), the dimensions of the grid. Each of the next $$$n$$$ lines contain $$$m$$$ space-separated strings describing the slippers in corresponding cells. Each slipper is described by a string of length 2. The first character is either "L" or "R", denoting left and right slipper respectively. The second character is one of "<", ">", "^" or "v". It means that the slipper initially faces left, right, forwards or backwards, respectively.
OutputPrint one integer: the maximum number of pairs of slippers that can be formed.
ExamplesInput2 2 R^ L> L< R^Output
2Input
3 2 L^ R^ R< L< L< R>Output
2Note
Consider the first sample. First, we rotate two left slippers: top counterclockwise, bottom clockwise. Second, we rotate two top slippers: left counterclockwise, right clockwise. After that we have two pairs of slippers in natural position: two in the top row and two in the bottom row.
R^ L> R< L> Rv Lv
L< R^ L^ R^ L^ R^
Here is another possible sequence of actions in this example, leading to a different final picture.
R^ L> R< Lv R< L>
L< R^ L< R^ L< R>