나만의 농장 운영하기: 밭 업그레이드

여러분에게 직사각형 모양의 땅이 주어진다. 땅에 미리 만들어져 있는 밭과 일꾼의 위치가 지도의 형태로 입력된다. 이 땅에 밭을 만들고 밭에 작물을 심어 수확하면서 농장을 운영해나가야 한다.

목표

이 문제는 2단계에 해당하는 문제이다. 2단계에선 밭을 업그레이드 할 수 있게 된다.

밭을 업그레이드 하면 해당 밭의 레벨이 올라가고, 특정 밭 레벨 이상에서만 심을 수 있는 작물이 존재한다.

밭을 업그레이드 하여 레벨 제한이 가장 높은 작물을 수확해보자.

구성

지도에는 다음의 것들이 표시되어있다:

• . : 빈 땅을 뜻한다. plow 명령을 써서 밭으로 만들 수 있다.
• # : 밭을 뜻한다. 밭에는 작물을 심을 수 있다. 처음부터 주어지는 밭은 모두 $1$레벨이다.

일꾼에 명령을 내려 밭을 만들거나 작물을 심고 수확할 수 있다. 명령을 수행하거나 작물이 성장하는 데는 시간이 필요하고, 이 게임에서 시간의 단위는 턴으로 표시된다. 입력이 주어진 시점에서 $0$턴으로 시작된다. 작물을 심거나 수확하는 데는 $1$턴이 소요되고 그 외의 경우는 입력으로 주어진다. 일꾼의 시작 위치는 입력으로 주어진다.

2단계 문제에서 일꾼이 할 수 있는 행동은 다음과 같다. (2단계에 추가된 행동부터 설명함)

• upgrade

  일꾼의 현재 위치에 있는 빈 밭을 한 레벨 업그레이드 한다. 업그레이드를 하려면 일꾼이 해당 업그레이드에 필요한 턴 동안 계속 밭에서 작업해야 한다.

  다음과 같은 경우 upgrade 명령을 수행할 수 없다.

  • 현재 위치에 밭이 없음
  • 업그레이드 할 돈이 부족
  • 밭에 작물이 자라는 중
  • 밭이 이미 최고 레벨인 경우

  레벨별로 업그레이드에 소요되는 턴과 비용은 입력으로 주어진다.

• move x y

  일꾼을 지정한 위치로 이동하게 한다. 일꾼의 현재 위치가 $x_0$, $y_0$ 일때 $|x-x_0|+|y-y_0|$ 턴이 지난 뒤 해당 위치에 도착한다. 지도의 작물이나 밭 등은 일꾼의 이동에 영향을 주지 않는다. 이동 중에는 다른 명령을 수행할 수 없다. ($|x|$는 $x$의 절대값)

• plow

  일꾼의 현재 위치에 새로 밭을 만든다. 반드시 일꾼의 현재 위치가 빈 땅이어야 한다. 밭을 만드는데 소요되는 비용과 턴은 입력으로 주어진다. 밭을 만드는데 필요한 턴 동안 일꾼이 계속 밭에서 작업해야 해서 다른 명령을 수행할 수 없다.

• plant crop

  일꾼의 현재 위치에 crop으로 지정된 이름의 작물을 심는다. 반드시 일꾼의 현재 위치가 작물의 레벨 제한 보다 크거나 같은 레벨의 빈 밭이어야 한다. 심는데는 $1$턴이 소요된다. $1$단계에서 심을 수 있는 작물 중에는 berry가 반드시 포함되어 있다. 작물을 심는데 필요한 비용만큼 현재 자금에서 사용된다. 심는 과정이 끝나면 수확할 때까지는 작물이 알아서 자라므로 일꾼을 다른 일을 시킬 수 있다. 작물이 완전히 자라는데 걸리는 턴은 입력으로 주어진다.

• harvest

  일꾼의 현재 위치에 완전히 자란 작물을 수확한다. 작물이 완전히 자란 경우만 수확이 가능하다. 수확에는 $1$턴이 소요된다. 수확이 완료되면 작물별 수확 후 얻을 수 있는 금액만큼 현재 자금이 증가하고, 작물이 자라던 밭은 빈 밭으로 돌아간다.

일꾼에게 명령을 내리는 방법은 출력 양식을 참고하라. 명령을 수행하는 중에는 다른 명령을 수행할 수 없다. 수행할 수 없는 명령을 내리거나 잘못된 명령을 내리는 경우 오답으로 처리된다.

입력

첫 줄에는 초기 자금 $M$과 밭의 최고 레벨 $L$이 주어진다. ($2 \le L \le 5$)

다음 줄에 밭을 만드는데 소요되는 턴과 비용이 주어진다. 새로 만들어진 밭은 항상 $1$레벨이다.

그 다음 $L-1$줄에 거쳐 순서대로 $1$에서 $2$레벨, $2$에서 $3$레벨, $\cdots$, $L-1$에서 $L$레벨로 업그레이드할 때 소요되는 턴과 비용이 주어진다.

그 다음 줄에 일꾼의 시작 가로 위치 $X$, 세로 위치 $Y$가 주어진다. 좌표는 지도의 왼쪽 제일 위 칸이 $(1, 1)$에 해당한다.

그 다음 줄에는 지도의 가로 크기 $W$와 세로 크기 $H$가 주어지고 다음 $H$줄에 거쳐 지도가 주어진다. ($1 \le W \le 100$, $1 \le H \le 100$)

그 다음 줄에 심을 수 있는 작물의 종류 개수 $N$이 주어진다. ($N \le 20$)

이어서 각 작물에 대한 입력이 $N$줄 들어온다.

작물별로 이름, 심을 수 있는 최소 밭 레벨, 수확할 수 있을 때까지 걸리는 턴, 심을 때 필요한 비용, 수확할 때 얻을 수 있는 금액이 주어진다. 작물의 이름은 띄어쓰기 없이 영어 소문자로만 이루어져 있고, $20$자를 넘지않는다.

자금을 저장할 때 $0$ 이상 $10$억 이하의 정수를 저장할 수 있는 자료형을 사용하면 문제를 해결하는데 충분할 것이다.

입력에는 밭 레벨 제한이 $L$인 작물이 하나 이상 존재한다. 항상 목표를 달성할 수 있는 입력만 주어진다.

출력

일꾼에게 특정 턴에 어떤 명령을 내릴지 턴 명령 명령인자의 형태로 한 줄에 하나씩 출력한다. 턴은 반드시 증가하는 순서로 출력하여야 한다.

출력된 명령을 수행하면 밭 레벨 제한이 $L$ 인 작물을 하나 이상 수확하도록 해야 한다.

수행할 수 없는 명령을 내리거나 잘못된 명령을 내리는 경우 오답으로 처리된다.

예제

100 3
5 50
5 100
5 150
3 2
3 2
...
...
2
berry 1 5 50 1000
watermelon 3 50 1000 10000

0 plow
5 plant berry
11 harvest
12 plant berry
18 harvest
19 upgrade
24 upgrade
29 plant watermelon
80 harvest

처음에 $100$원을 가지고 시작한다.

밭의 최고 레벨은 $3$이다.

새 밭을 만들려면 $5$턴, $50$원이 필요하다.

밭을 $1$레벨에서 $2$레벨로 업그레이드하려면 $5$턴, $100$원이 필요하다.

밭을 $2$레벨에서 $3$레벨로 업그레이드하려면 $5$턴, $150$원이 필요하다.

일꾼은 $(3, 2)$ 위치에서 시작한다.

지도의 크기는 가로 $3$, 세로 $2$ 이다. 밭이 없는 지도가 주어졌다.

심을 수 있는 작물 $2$개가 주어진다:

• berry: 자라는데 $5$턴, 심으려면 $50$원이 필요하고 수확하면 $1\,000$원을 얻는다.
• watermelon: $3$레벨 이상 밭에서만 심을 수 있으며 자라는데 $50$턴, 심으려면 $1\,000$원이 필요하고 수확하면 $10\,000$원을 얻는다.

하나씩 살펴보자. 현재 위치에 새 밭을 만들었다. (남은 자금 $50$원)

berry를 심은 후 (남은 자금 $0$원) 수확했다. (남은 자금 $1\,000$원)

한 번 더 심은 후 수확하여 남은 자금을 $1\,950$원을 만들었다.

밭을 $1$레벨에서 $2$레벨로 업그레이드 했다. (남은 자금 $1\,850$원)

밭을 $2$레벨에서 $3$레벨로 업그레이드 했다. (남은 자금 $1\,700$원)

watermelon을 심고 (남은 자금 $700$원) 기다린 후 수확했다. ($10\,700$원)

$3$레벨 작물을 수확했으므로 문제의 목표를 완수했다.

채점 규칙

모든 숨겨진 입력 데이터에 대해 정답이면 만점을 주고, 하나라도 틀리면 점수를 주지 않는다.