H to O

Cesium 교수는 어떤 화학 물질을 다른 화학 물질로 바꾸고 잔여물을 남기는 새로운 공정을 개발했다. 과정은 단순하다. A형 분자를 주어진 개수만큼 입력하고, 원하는 출력형 B를 지정한 뒤 기계를 켜면 된다. 그러면 기계는 B형 분자를 최대한 많이 만든다. 그런데 Cadmium 교수가 이 연구를 시기해 기계의 전선을 반대로 연결해 방해하려 했다. Cesium 교수는 조수의 연락을 받고 실수를 고쳤다. 앞으로 문제를 찾아내기 위해, 교수는 기계가 출력해야 할 분자 수를 자동으로 계산하는 방법을 의뢰한다. 이 알고리즘이 있으면 소중한 기계가 조작되었는지 판별할 수 있다.

분자는 대문자와 숫자로 이루어진 문자열로 쓴다. 대문자는 원자를 나타낸다. Cesium은 원자 기호로 알파벳 한 글자만 쓰므로 H, C, A, X, Y, ... 는 쓸 수 있지만 He, Mg, ... 는 쓸 수 없다. 글자 뒤에 숫자가 없으면 그 원자가 한 개 있다는 뜻이다. 원자 뒤에 숫자 l (1 ≤ l < 10^3)이 오면 그 원자가 l개 있다는 뜻이다. 원자는 화학 물질 안에 여러 번 나타날 수 있다.

예를 들어 H2OC100H는 H 원자 2개, 그다음 O 원자 1개, 그다음 C 원자 100개, 다시 H 원자 1개를 뜻한다.

• 첫째 줄에는 입력 분자가 주어진다. 길이 2500 이하인 문자열 뒤에 정수 1 ≤ k ≤ 10^3이 오며, Cesium 교수가 가진 그 분자의 개수를 나타낸다.
• 둘째 줄에는 원하는 출력 분자가 주어진다. 길이 2500 이하인 문자열이다.

입력 분자로 만들 수 있는 출력 분자의 최대 개수 n을 한 줄에 출력한다.