Corrida de Rua

A Quadradônia foi escolhida para sediar uma prova internacional de corrida de rua. As ruas da Quadradônia são todas alinhadas aos eixos Norte-Sul e Leste-Oeste. As quadras da cidade são quadradas, todas de mesma dimensão. A partida e a chegada da corrida são em uma mesma interseção de ruas.

Para realizar a corrida será necessário cercar a área da cidade onde será feito o percurso. A cerca será colocada a no mínimo uma quadra de distância de qualquer ponto do percurso da corrida, e deve ser retilínea e alinhada aos eixos.

As figuras (a) e (b) abaixo mostram mapas da cidade ilustrando duas possibilidades de percurso e respectivas possibilidades de cercas.

Dado o percurso da corrida, sua tarefa é escrever um programa para determinar o menor comprimento possível da cerca, em número de quadras.

Entrada

A primeira linha contém um inteiro $N$, o número de segmentos que definem o percurso da corrida. As $N$ linhas seguintes descrevem os segmentos, na ordem em que são percorridos na corrida, a partir do ponto de partida/chegada. Cada linha contém um inteiro $C_i$ e um caractere $D_i$, indicando respectivamente o comprimento do segmento, em número de quadras, e a direção do segmento, onde N indica Norte, S indica Sul, L indica Leste e O indica Oeste.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o menor comprimento possível da cerca, em número de quadras.

Restrições

• $2 \leq N \leq 100\ 000$
• $1 \leq C_i \leq 10\ 000$ para $1 \leq i \leq N$
• $D_i$ é N, S, L ou O para $1 \leq i \leq N$

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

• Subtarefa 1 (11 pontos): $N = 2$, ou seja, o percurso utiliza uma única rua. (Veja o exemplo de entrada 1.)
• Subtarefa 2 (30 pontos): $N \leq 1\ 000, C_i\leq 1\ 000$ e $P_i\leq 1\ 000$
  • $D_i=\$ N ou L para $1 \leq i \leq N - 2$
  • $D_{N-1}=\$S
  • $D_N=\$O

Ou seja, o percurso da corrida forma uma escadinha. (Veja os exemplos de entrada 3 e 4.)

• Subtarefa 3 (25 pontos):
  • $N \leq 100$
  • $C_i \leq 10$ para $1 \leq i \leq N$
• Subtarefa 4 (34 pontos): Nenhuma restrição adicional.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

2
7 L
7 O

Exemplo de saída 1

22

Explicação do exemplo 1: O percurso consiste de uma única rua. A figura abaixo ilustra o percurso e a menor cerca possível, que tem comprimento de 22 quadras.

Exemplo de entrada 2

8
2 L
3 S
3 L
3 N
2 L
5 S
7 O
5 N

Exemplo de saída 2

32

Explicação do exemplo 2: O percurso consiste de oito segmentos. A figura abaixo ilustra o percurso e a menor cerca possível.

Exemplo de entrada 3

8
3 N
1 L
1 N
2 L
1 N
3 L
5 S
6 O

Exemplo de saída 3

30

Explicação do exemplo 3: A figura abaixo ilustra o percurso, que tem 8 segmentos. A menor cerca possível para esse percurso tem comprimento 30 quadras. Observe que esse exemplo e o próximo satisfazem às restrições da subtarefa 2.

Exemplo de entrada 4

8
2 N
2 L
2 N
3 L
1 N
1 L
5 S
6 O

Exemplo de saída 4

30

Explicação do exemplo 4: A figura abaixo ilustra o percurso, que tem 8 segmentos. A menor cerca possível para esse percurso tem comprimento 30 quadras. Observe que esse exemplo satisfaz às restrições da subtarefa 2.

Exemplo de entrada 5

7
5 L
3 S
3 O
5 N
4 O
2 S
2 L

Exemplo de saída 5

32

Explicação do exemplo 5: Esse é o exemplo da figura (b) do enunciado. A menor cerca possível para esse percurso é 32 quadras.