돌도끼 만들기

모바일 MMORPG ＜야생의 땅: 듀랑고＞ 에서는 플레이어들이 낯선 세상에서 생존하기 위해 필요한 물건들을 자연에서 채집하거나, 직접 만들어야 한다. 예를 들어, 다음과 같은 규칙을 따라 물건을 얻을 수 있다고 하자.

• 나뭇가지는 $1$개씩 자연에서 직접 채집할 수 있다 (에너지 $10$ 필요)
• 갈대는 $1$개씩 자연에서 직접 채집할 수 있다 (에너지 $5$ 필요)
• 돌은 $1$개씩 자연에서 직접 채집할 수 있다 (에너지 $5$ 필요)
• 나뭇가지 $1$개로 나무막대 $1$개를 만들 수 있다 (에너지 $10$ 필요)
• 돌 $1$개, 나무막대 $1$개, 갈대 $2$개로 돌도끼 $1$개를 만들 수 있다 (에너지 $50$ 필요)

이 경우 돌도끼 $1$개를 만드는 방법의 예를 들면 다음과 같다:

갈대 $2$개를 채집하고(에너지 $5 \times 2 = 10$ 소모), 나뭇가지 $1$개를 채집하여(에너지 $10$ 소모) 나무막대 $1$개로 바꾸고(에너지 $10$ 소모), 돌 $1$개를 채집하고(에너지 $5$ 소모), 이 재료들로 돌도끼 $1$개를 만든다(에너지 $50$ 소모). 총 에너지 소모량은 $10 + 10 + 10 + 5 + 50 = 85$이다.

물건을 얻을 수 있는 규칙들이 주어질 때, 돌도끼를 만들기 위해서는 어떤 순서로 일을 해야 하는지 구하는 프로그램을 작성하라.

입력 형식

첫째 줄에 물건을 얻을 수 있는 규칙의 개수를 나타내는 자연수 $N$ ($1 \le N \le 50$)이 주어진다.

다음 $N$줄에 걸쳐서 물건을 만드는 규칙을 나타내는 입력이 주어진다.

$i$번째 줄에는, $i$번째 규칙이 $k$ $m_1$ $c_1$ $m_2$ $c_2$ $\cdots$ $m_k$ $c_k$ $E$ $M$의 형태로 주어진다. 이는 $k$($0 \le k \le 4$)개의 재료 $m_1$, $m_2$, $\cdots$, $m_k$를 각각 $c_1$, $c_2$, $\cdots$, $c_k$ ($1 \le c_i \le 10$)개 사용하고 $E$($1 \le E \le 100$)만큼의 에너지를 소모하면 $M$을 $1$개 만들 수 있다는 의미다. $k = 0$이면 $E$만큼의 에너지를 소모하여 자연에서 직접 채집할 수 있다는 의미다.

$k$, $c_i$, $E$는 모두 정수이다. $M$ 은 알파벳 소문자로 이루어진 길이 $1$이상 $16$이하의 문자열이고, $m_1$, $m_2$, $\cdots$, $m_k$는 반드시 이전 줄에 주어진 $M$중 하나이다. 같은 물건을 만드는 규칙이 여럿 주어질 수 있다.

주어진 $M$중에는 반드시 stoneaxe가 존재하며, 이 물건이 돌도끼를 나타낸다. 돌도끼 하나를 만드는 최적의 에너지량이 $10^{16}$이하인 입력만 주어진다.

출력 형식

첫째 줄에 돌도끼를 만드는 과정의 총 절차 개수 $K$를 첫 줄에 출력한다. $K$는 $1$이상 $100$이하의 자연수여야 한다.

다음 $K$줄에 걸쳐 원하는 물건을 만드는 과정을 출력하는데, 순서대로 몇 번째 규칙을 연속적으로 몇 번 사용할 것인지 공백 하나로 구분하여 출력하면 된다. 규칙을 사용하는 횟수는 $1$이상 $10^{16}$이하여야 한다. 또한 특정 규칙을 사용할 때는, 필요한 재료가 이미 모두 만들어져 있어야 한다.

예제 1

5
0 10 branch
0 5 reed
0 5 stone
1 branch 1 10 woodstick
3 stone 1 woodstick 1 reed 2 50 stoneaxe

5
2 2
1 1
4 1
3 1
5 1

예제 2

3
0 8 stone
1 stone 2 1 stone
1 stone 3 3 stoneaxe

2
1 3
3 1

예제 설명

예제 1은 문제 설명에서 주어진 예제와 같다.

예제 2에서 2번 규칙을 적용하면 힘들여 만든 돌의 개수를 줄이기만 하므로 쓸모가 없다. 그러므로 1번 규칙과 3번 규칙만을 이용하여 돌도끼를 만들면 된다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

단, 출력에 잘못된 내용이 없고, 출력의 결과로 돌도끼가 하나 만들어 졌다면 점수의 절반을 받는다. 사용한 에너지량이 최소가 되면 전체 점수를 얻을 수 있다.

해설