계산기

Christian Horvat의 이미지, commons.wikimedia.org에서 가져옴

Reiknibíllinn에서는 모든 일이 순조롭게 진행되고 있었지만, 갑자기 계산기의 배터리가 다 닳아 버렸다! 잊어서는 안 되는 매우 중요한 수가 그 계산기에 입력되어 있었으므로, 이를 즉시 해결해야 한다. 다행히 그 수는 기억하고 있지만, 가장 큰 문제는 그 수를 계산기에 다시 입력하는 것이다. 계산기는 다소 원시적이어서 몇 가지 연산만 지원한다.

계산기가 지원하는 연산을 이용해 주어진 수를 입력하는 방법을 알아낼 수 있는가? 계산기에는 $8$자리만 들어가므로, 연산 결과가 $8$자리에 들어가지 않으면 계산기가 고장 나고 모든 것을 처음부터 다시 시작해야 한다! 결과가 음수일 때도 마찬가지이며, 계산기는 음수도 지원하지 않는다. 계산기를 처음 켜면 수 $0$이 표시된다.

계산기의 충전량이 상당히 부족하므로, 가능한 한 효율적으로 이 작업을 수행하고자 한다. 가능한 한 효율적으로 수를 입력할 때 얼마만큼의 충전량을 소모해야 하는가?

채점

그룹 | 점수 | 제약 조건

1 | 15 | 가능한 연산은 +와 *뿐이며, $X \leq 1\,000$.

2 | 15 | 가능한 연산은 +와 *뿐이다.

3 | 40 | $c \leq 1$.

4 | 30 | 추가 제약 조건이 없다.

입력의 첫째 줄에는 두 정수 $A, X$가 주어진다. $A$은 계산기가 지원하는 연산의 개수이고, $X$은 계산기에 입력하려는 중요한 수이다. 항상 $1 \leq A \leq 5$ 및 $0 \leq X < 10^8$가 성립한다. 그다음에는 각각 하나의 연산을 설명하는 $A$개의 줄이 주어진다. 각 줄에는 op, $y$, $c$가 주어지며, 여기서 $y, c$은 정수이고 op는 기호 +, -, *, / 중 하나이다. 이는 이 연산이 계산기의 현재 값을 첫 번째 수로 삼아, 계산기의 현재 값과 $y$에 op을 적용한다는 뜻이다. 따라서 +와 $y = 5$는 계산기의 현재 값에 $5$를 더한다. $c$는 이 연산을 수행하는 데 필요한 충전량을 나타낸다. 항상 $0 \leq y \leq 9$ 및 $0 \leq c \leq 3$가 성립한다. 기호가 /이면 $y \neq 0$이다. 나눗셈은 정수 나눗셈이므로 결과는 $0$ 방향으로 반올림된다.

수 $X$에 도달하는 데 필요한 최소 충전량 소모를 출력한다. 계산기에 수 $X$를 표시할 방법이 없다면, 대신 Engin leid!을 출력한다.