수확의 계절이다!
시간 제한2초메모리 제한1024 MB
주어진 N개의 방향과 횟수만큼 씨앗을 뿌리며 지나간 칸을 수확해 다시 심을 때, 납품량 K를 만족하는 최대 성장 시간 x를 구한다.
문제
개발이 지긋지긋해져 귀농을 결심한 성현이는 저금해둔 돈을 모두 털어 무한하게 큰 농지를 구매하였다. 농지는 정사각형 타일로 이루어진 2차원의 격자판이다.
성현이는 처음에 농지의 임의의 지점에서 출발하여 진행 방향과 횟수를 정해 이동하며 씨앗을 뿌린다. 예를 들어, 진행 방향이 E(동쪽)이고 씨앗을 뿌리는 횟수가 이라면, 동쪽으로 칸 이동하고 현재 자리에 씨앗을 뿌리는 두 작업을 한 세트로 하여 세트를 수행하게 된다. 이동하는데 의 시간, 씨앗을 뿌리는데 의 시간이 걸리므로 앞의 예시에서 세트를 수행하는데 걸리는 시간은 이다. 만약 이동을 하는 도중 기존에 씨앗을 뿌린 곳을 다시 지나게 된다면, 현재 자리에 있는 작물을 수확하고 그 곳에 다시 씨앗을 뿌리거나 수확을 하지 않고 지나칠 수 있다. 만약 수확을 하지 않았다면 남는 자리가 없어 씨앗을 뿌리지 못하고 다음 지점으로 이동하게 된다. 수확하는데 걸리는 시간은 이므로 한 세트에서 수확과 씨를 뿌리는 작업을 모두 하더라도 의 시간이 걸린다. 씨앗은 각 품종마다 작물이 완전히 자라나는데 걸리는 시간 는 양의 정수가 있으며, 씨앗을 뿌린 후 시간이 지나기 전에 수확한 작물은 상품 가치가 없으므로 폐기하게 된다. 씨앗을 뿌린지 시간 이상 지난 작물을 수확한다면 작물 하나를 납품할 수 있다.
성현이는 올해의 일을 끝냈을 때 납품해야 하는 작물의 양이 총 보다 크거나 같아야 하며, 만약 넘기지 못한다면 파산하게 된다. 가 클수록 저렴한 품종의 씨앗인 것을 아는 성현이는, 최대한 저렴한 품종을 사용하면서 올해의 납품량을 만족시킬 수 있는 최대의 를 구하려고 한다.
입력
첫 번째 줄에 올해 할 일의 세트 수 과 납품량 가 공백으로 구분되어 주어진다.
두 번째 줄부터 개의 줄에 진행 방향 와 진행 횟수 가 공백으로 구분되어 주어진다. 는 동서남북을 나타내는 E, W, S, N 중 하나;
출력
올해의 납품량을 만족시킬 수 있는 최대의 를 출력하라.
어떠한 상황에서도 납품량을 만족하지 못하면 을 출력한다.