마비노기 인벤토리

마비노기의 인벤토리는 다른 게임의 인벤토리와는 달리 아이템마다 특정 크기를 갖고 있고, 각각 크기에 맞추어 인벤토리의 원하는 위치에 겹치지 않게 배치할 인벤토리에 배치할 수 있다.

아래 <그림 1>은 실제 마비노기 인벤토리의 스크린샷이다.

현재 재성이의 인벤토리는 세로 길이 $H$, 가로 길이 $W$로 $H\times W$ 크기이다. 재성이는 은행에서 미리 모아놓은 양털과 나무장작을 찾아 상점에 가서 팔려고 한다. 양털 하나를 상점에 팔 때 $A$원을 받을 수 있고, 나무장작 하나를 상점에 팔 때 $B$원을 받을 수 있다. 은행과 상점을 왕복하는 것은 매우 번거로운 일이므로 한번에 최대한 많은 돈을 벌 수 있도록 인벤토리에 넣어 이동하고 싶다.

이 때 양털과 나무장작은 각각 $2 \times 2$, $3 \times 1$ 크기를 차지한다. 아이템은 인벤토리 내의 공간에 다른 아이템과 겹치지 않게 어디에든 배치할 수 있지만 아이템을 회전할 수는 없다. 즉, 나무장작을 $90$도 회전해서 $1 \times 3$으로 배치할 수 없다. (문제에 주어진 시뮬레이터의 내용을 참고하면 좋다.)

인벤토리의 크기와 원래 있던 아이템들에 대한 정보가 주어졌을 때, 은행에서 상점을 한 번 갈 때 최대한 많은 돈을 벌어보자. 단, 원래 있던 아이템은 재배치할 수 없다.

입력 형식

첫 줄에 인벤토리의 세로 크기 $H$, 가로 크기 $W$, 양털 하나의 가격 $A$, 나무장작 하나의 가격 $B$가 공백으로 구분되어 주어진다. ($1 \le H, W \le 18$; $0 \le A, B \le 10\,000$)

그다음 $H$개의 줄에 걸쳐 $H\times W$ 크기의 인벤토리에 대한 정보가 주어진다. -는 인벤토리에서 빈칸을 나타내고, X는 인벤토리에 이미 다른 아이템이 놓여있음을 의미한다.

출력 형식

첫 줄에 은행에서 상점을 한 번 갈 때 최대한 많이 벌 수 있는 돈의 액수와 그 때 담은 양털의 개수 $s$와 나무장작 개수 $w$를 공백으로 구분하여 출력한다.

그 다음 $s$개 줄에 걸쳐 각 줄에 양털을 놓은 인벤토리 왼쪽 위 좌표를 행 번호, 열 번호 순서대로 출력한다. 다음에는 $w$개 줄에 걸쳐 각 줄에 나무장작을 놓은 인벤토리 왼쪽 위 좌표를 행 번호, 열 번호 순서대로 출력한다.

만약, 가능한 답이 여러 가지라면 그중 아무거나 하나 출력한다.

예제 1

5 5 4 4
XXXXX
X---X
X---X
X---X
XXXXX

12 0 3
2 2
2 3
2 4

예제 2

5 5 4 4
XXXXX
X--XX
X--X-
XXXX-
XXXX-

8 1 1
2 2
3 5

채점 방식

이 문제는 풀이 소스코드를 제출하지 않고, 각 테스트케이스의 입력데이터를 다운받아 알맞은 출력 파일을 만들어 출력 파일만을 제출하는 문제다.

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

해설