34754번 - 닷지 테이블

문제

준호는 4ドル \times 4$ 크기의 격자판에서 총 $K$초 동안 매 초마다 적의 공격이 발생하는 피하기 게임을 하고 있다.

공격은 $d$ $s$ $r$ $p$의 형식으로 주어지며 자세한 내용은 다음과 같다.

• 공격은 방향 $d$(위, 아래, 왼쪽, 오른쪽 중 하나를 뜻하는 UDLR 중 한 글자)에서 시작한다.
• 공격은 방향이 L, R일 경우 $s$행에 발생하고 U, D일 경우 $s$열에 발생한다.
• 시작 지점을 기준으로 해당 방향으로 $r$칸만큼의 범위에 걸쳐 공격이 발생한다. 예를 들어 공격의 방향이 $U$일 경우, $s$열의 1ドル$행부터 $r$행까지의 공간에 공격이 발생한다.
• 공격이 발생한 칸은 공격 발생 시점부터 $p$초 동안, 즉 시각 $t$에 공격이 발생했다면 시각 $t, t+1, \dots, t+p-1$까지 공격이 남는다. 이미 공격이 남아 있는 칸에 새로운 공격이 발생할 경우, 두 공격 중 더 늦게 사라지는 공격의 시간까지 공격이 유지된다.

준호는 처음에 격자의 어느 칸에서든 시작할 수 있고 1ドル$초마다 격자판 안의 상하좌우 네 방향 중 한 곳의 인접한 칸으로 이동하거나 가만히 있을 수 있다. 준호는 $K$초 동안 주어진 공격과 잔상을 피해 다녀야 하며, 게임 도중 공격이 발생한 칸에 있는 경우 그 초에는 공격을 맞은 것으로 간주한다.

아래 그림은 4ドル$초 동안 진행되는 게임의 예시이다.

준호가 공격에 최대한 덜 맞기 위해 최적으로 이동한다고 할 때, 최소 몇 초 동안 공격을 맞게 되는지 구해보자.

입력

첫 번째 줄에 게임이 진행되는 시간 $K$가 주어진다. $(1 \le K \le 200,000円)$

두 번째 줄부터 $K$개의 줄에 공격을 의미하는 $d,ドル $s,ドル $r,ドル $p$가 공백으로 구분되어 주어진다. $(d \in \{$U, D, L, R$\};$ 1ドル \le s, r \le 4;$ 1ドル \le p \le K)$

입력으로 주어지는 수는 모두 정수이다.

출력

첫 번째 줄에 공격을 맞게 되는 최소 시간을 출력한다.

제한

노트