25909번 - 수확의 계절이다!

개발이 지긋지긋해져 귀농을 결심한 성현이는 저금해둔 돈을 모두 털어 무한하게 큰 농지를 구매하였다. 농지는 정사각형 타일로 이루어진 2차원의 격자판이다.

성현이는 처음에 농지의 임의의 지점에서 출발하여 진행 방향과 횟수를 정해 이동하며 씨앗을 뿌린다. 예를 들어, 진행 방향이 E(동쪽)이고 씨앗을 뿌리는 횟수가 $10$이라면, 동쪽으로 $1$칸 이동하고 현재 자리에 씨앗을 뿌리는 두 작업을 한 세트로 하여 $10$세트를 수행하게 된다. 이동하는데 $1$의 시간, 씨앗을 뿌리는데 $0$의 시간이 걸리므로 앞의 예시에서 $10$세트를 수행하는데 걸리는 시간은 $10$이다. 만약 이동을 하는 도중 기존에 씨앗을 뿌린 곳을 다시 지나게 된다면, 현재 자리에 있는 작물을 수확하고 그 곳에 다시 씨앗을 뿌리거나 수확을 하지 않고 지나칠 수 있다. 만약 수확을 하지 않았다면 남는 자리가 없어 씨앗을 뿌리지 못하고 다음 지점으로 이동하게 된다. 수확하는데 걸리는 시간은 $0$이므로 한 세트에서 수확과 씨를 뿌리는 작업을 모두 하더라도 $1$의 시간이 걸린다. 씨앗은 각 품종마다 작물이 완전히 자라나는데 걸리는 시간 $x(x$ 는 양의 정수$)$가 있으며, 씨앗을 뿌린 후 $x$시간이 지나기 전에 수확한 작물은 상품 가치가 없으므로 폐기하게 된다. 씨앗을 뿌린지 $x$시간 이상 지난 작물을 수확한다면 작물 하나를 납품할 수 있다.

성현이는 올해의 일을 끝냈을 때 납품해야 하는 작물의 양이 총 $K$보다 크거나 같아야 하며, 만약 넘기지 못한다면 파산하게 된다. $x$가 클수록 저렴한 품종의 씨앗인 것을 아는 성현이는, 최대한 저렴한 품종을 사용하면서 올해의 납품량을 만족시킬 수 있는 최대의 $x$를 구하려고 한다.

첫 번째 줄에 올해 할 일의 세트 수 $N$과 납품량 $K$가 공백으로 구분되어 주어진다. $(1\leq N\leq1\,000; 1\leq K\leq1\,000\,000)$

두 번째 줄부터 $N$개의 줄에 진행 방향 $a$와 진행 횟수 $b$가 공백으로 구분되어 주어진다. $(a$는 동서남북을 나타내는 E, W, S, N 중 하나; $1\leq b\leq1\,000)$

올해의 납품량을 만족시킬 수 있는 최대의 $x$를 출력하라.

어떠한 상황에서도 납품량을 만족하지 못하면 $-1$을 출력한다.