33925번 - 쿠키런

문제

과거 쿠키런 최고 권위자로 이름을 날렸던 안뇽이는 한때 최애 게임이었던 쿠키런이 벌써 12주년을 맞았다는 소식을 듣고 복귀 유저가 되었다!

쿠키런의 스테이지는 3ドル \times N$ 크기의 2ドル$차원 배열로 구성되어 있으며, 플레이어(쿠키)는 1ドル$번 열(왼쪽 끝)에서 출발해 $N$번 열(오른쪽 끝)에 도착해야 한다.

스테이지의 임의의 열에는 3ドル \times 1$ 크기의 장애물이 있으며, 장애물은 낮은 장애물, 높은 장애물, 상단 장애물 3ドル$종류가 있다.

각 장애물은 ‘^’, ‘.’, ‘v’의 조합으로 이루어져 있으며, 낮은 장애물은 점프를 1ドル$번 사용해, 높은 장애물은 점프를 2ドル$번 사용해, 상단 장애물은 슬라이드를 1ドル$번 사용해 각각 피할 수 있다. 점프나 슬라이드를 사용해 장애물을 회피한 후에는 직전의 점프나 슬라이드 상태가 유지되지 않는다.

출발점인 1ドル$번 열과 도착점인 $N$번 열에는 장애물이 존재하지 않으며, $k$번 열에 장애물이 존재한다면 바로 뒤 $k + 1$번 열에는 장애물이 연속하게 존재하지 않는다.

게임 시작 시점 처음 쿠키의 체력은 $H$이며, 장애물의 종류와 관계없이 장애물에 1ドル$번 부딪힐 때마다 체력이 $K$만큼 감소한다. 이때 체력이 0ドル$ 이하가 되면 스테이지 클리어에 실패하며, 그렇지 않다면 다음 열로 이동한다. 만약 쿠키가 무사히 $N$번 열에 도착한다면 스테이지 클리어에 성공한다.

쿠키런 고인물인 안뇽이는 발가락으로도 스테이지를 클리어할 수 있다고 자신했다. 하지만 안뇽이는 발가락이 짧아서 실제로 발가락으로 게임을 할 수는 없었기 때문에, 결국 고민 끝에 안뇽이는 점프를 $J$번 이하, 슬라이드를 $S$번 이하로만 사용해 스테이지를 클리어해보기로 마음먹었다.

3ドル \times N$ 크기의 스테이지가 주어질 때, 안뇽이가 스테이지를 클리어했을 때의 최대 체력을 구해보자.

입력

첫 번째 줄에 정수 $N, J, S, H, K$가 공백으로 구분되어 주어진다.

이어서 3ドル$줄에 걸쳐 스테이지의 정보가 주어진다.

출력

안뇽이가 점프를 $J$번 이하, 슬라이드를 $S$번 이하로 사용해 스테이지를 클리어했을 때의 최대 체력을 출력한다.

만약 안뇽이가 스테이지를 클리어할 수 없다면 대신 -1을 출력한다.

제한

• 3ドル \le N \le 100$
• 0ドル \le J \le 10$
• 0ドル \le S \le 10$
• 1ドル \le H \le 200$
• 1ドル \le K \le 10$

힌트