H to O

Professor Cesium has created a new process that turns one chemical product into another, leaving some residue behind. The process is simple: he enters a given number of molecules of type A, specifies the desired output type B, and starts the machine. The machine then produces as many molecules of type B as it can. Unfortunately, Professor Cadmium was jealous of this work and tried to sabotage the machine by reversing some wires. Professor Cesium, alerted by an assistant, managed to repair the damage. To catch any future tampering, he asks you to write an automatic way to compute how many molecules the machine should output. With this algorithm he can detect whether his machine has been altered.

Molecules are written as strings of uppercase letters and numbers. Uppercase letters represent atoms. Cesium uses only single letters of the alphabet as atom abbreviations, so H, C, A, X, Y, ... are valid, while He, Mg, ... are not. A letter not followed by a number means there is one atom of it. An atom followed by a number l (1 ≤ l < 10^3) represents l copies of that atom. An atom may appear multiple times in a chemical product.

For example, H2OC100H means 2 atoms of H, then 1 of O, then 100 of C, then 1 of H again.

• The first line contains the input molecule, a string of length at most 2500, followed by an integer 1 ≤ k ≤ 10^3, the number of such molecules Professor Cesium has.
• The second line contains the desired output molecule, a string of length at most 2500.

Print a single line with the maximum number n of output molecules that can be built from the input molecules.