문제
농부 존은 그의 농장을 관리하는 모든 면에서 꽤나 신뢰할 만하지만, 한 가지를 제외하면 그렇지 않다: 그는 제때에 또는 논리적인 방식으로 잔디를 깎는 데 형편없다.
농장은 정사각형 단위 칸들로 이루어진 큰 2차원 격자이다. FJ는 시간 t = 0에 이 칸들 중 하나에서 시작하며, 이 칸의 잔디를 깎아 처음에는 이 칸만 잔디가 깎여 있는 상태가 된다. FJ의 나머지 잔디 깎기 패턴은 N개의 명령으로 구성된 순서로 주어진다. 예를 들어, 첫 번째 명령이 "W 10"이라면, 시간 t = 1부터 t = 10까지(즉, 다음 10 단위 시간 동안), FJ는 매 시간 서쪽으로 한 칸 이동하며, 그 경로를 따라 잔디를 깎는다. 이러한 이동 단계를 완료하면, 그는 시간 t = 10에 서쪽으로 10칸 떨어진 곳에 도달하며, 그 사이의 모든 칸의 잔디를 깎게 된다.
FJ의 진척 속도가 너무 느려서, 그가 모든 잔디를 다 깎기 전에 이미 깎은 잔디의 일부가 다시 자랄 수도 있다. 어떤 잔디 조각이 시간 t에 깎였다면, 그것은 시간 t + x에 다시 자라난다.
FJ의 잔디 깎기 패턴은 그가 같은 칸을 여러 번 방문하게 할 수도 있지만, 그는 이미 잔디가 깎여 있는 칸을 다시 마주치는 일은 절대 없다고 말한다. 즉, 그가 어떤 칸을 방문할 때마다, 그 칸을 가장 최근에 방문한 시점은 적어도 x 단위 시간 이상 이전이어야 하며, 그래야 잔디가 다시 자랐을 것이다.
FJ의 관찰이 계속해서 성립할 수 있도록 하는 x의 최대 가능한 값을 구하시오.
입력
입력의 첫 번째 줄에는
나머지
출력
FJ가 결코 잔디가 깎여 있는 칸을 밟지 않도록 하는 x의 최대 값을 구하시오. 만약 FJ가 어떤 칸도 두 번 이상 방문하지 않는다면, -1을 출력하시오.
예제
6
N 10
E 2
S 3
W 4
S 5
E 8
10
이 예시에서, FJ는 시간 7에 이미 밟았던 칸을 시간 17에 다시 밟는다. 따라서 x는 많아야 10이어야 하며, 그렇지 않으면 첫 방문에서 깎인 잔디가 아직 다시 자라지 않았을 것이다. 그는 또한 시간 2에 방문했던 칸을 시간 26에 다시 밟는다. 그러므로 x는 또한 많아야 24이어야 한다. 이 두 제약 중 첫 번째가 더 엄격하므로, x는 많아야 10임을 알 수 있다.
로그인해야 코드를 작성할 수 있어요.