댄스 패드

댄스 패드는 위쪽, 오른쪽, 아래쪽, 왼쪽을 가리키는 네 개의 화살표로 구성된다. 댄스 게임을 할 때는 음악의 박자에 맞춰 밟아야 하는 화살표의 순서가 주어진다. 때로는 같은 박자에 두 개의 화살표가 표시될 수 있으므로, 두 화살표를 밟기 위해 점프해야 한다. 어떤 박자에 화살표를 누를 필요가 없더라도 발 하나를 그 화살표 위에 계속 올려 두어도 된다.

댄스 패드.

Johan은 거의 매일 자신의 댄스 패드 위에서 뛰어다니지만, 때로는 발을 움직이며 박자를 따라가는 것을 어려워한다. 그래서 그는 곡을 최적으로 플레이하는 데 도움을 받고 싶어 한다. 이는 발을 새로운 화살표로 움직이는 횟수를 가능한 한 적게 한다는 뜻이다.

게임을 시작할 때 그의 왼발은 왼쪽 화살표 위에 있고, 오른발은 오른쪽 화살표 위에 있다.

곡과 각 박자마다 눌러야 하는 하나 또는 두 개의 화살표가 주어질 때, Johan이 발을 다른 화살표로 움직여야 하는 최소 횟수를 계산한다. 점프하면서 두 발을 모두 움직여도 여전히 두 번의 움직임으로 센다.

채점

제출한 해답은 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한 조건

$1$ |$20$| $N \le 10$이고 Johan은 박자마다 화살표 하나만 누르면 된다.

$2$ |$30$| Johan은 박자마다 화살표 하나만 누르면 된다.

$3$ |$50$| 추가 제한 조건이 없다.

첫 번째 줄에는 곡의 박자 수를 나타내는 정수 $N$ ($1 \le N \le 10\,000$)이 주어진다.

이어서 각 박자마다 한 줄씩, $N$개의 줄이 주어진다. 각 박자는 U, H, N, V 중 하나 또는 두 개의 문자로 이루어진 문자열이며, 각각 위쪽'', 오른쪽'', 아래쪽'', 왼쪽''을 의미한다. 이들은 해당 박자에 눌러야 하는 화살표이다.

Johan이 움직여야 하는 최소 횟수를 나타내는 정수를 출력한다.

Johan은 언제나 그렇듯이 왼쪽과 오른쪽 화살표 위에 발을 올려 둔 상태로 시작한다. 가능한 최적해는 다음과 같다. 첫 번째 박자에는 오른발을 위쪽 화살표로 움직인다. 그런 다음 오른발을 다시 아래쪽 화살표로 움직인다. 다음 두 번의 움직임에서는 이미 왼쪽 화살표 위에 발 하나가 있으므로 발을 움직이지 않고, 마지막으로 어느 쪽이든 한 발을 오른쪽 화살표로 움직인다. 여기에는 $3$번의 움직임이 필요하다.