Banking II

The Actuarial Commerce Merchant bank hands you a pattern word every time you log in, and the word contains only upper and lower case letters. You use it to extract digits from your PIN and add them up.

Every letter of the pattern word is a number: a (or A) is 1, b (or B) is 2, and in the same way z (or Z) is 26. A lower case letter is a count of digits to extract from the PIN, an upper case letter is a count of digits to skip. The letters are processed from left to right, which produces a sequence of extracted digits, and the sum of that sequence is the number you type into the field on the web page form.

Say your PIN is 1093373 and the pattern word is aBcA. You extract one digit (1), skip two digits (09), extract three digits (337), then skip one digit (3). The extracted digits are 1, 3, 3 and 7, so you type 14.

A PIN holds up to 256 digits, and the bank only issues a pattern word whose letters, read as numbers, sum to the length of the PIN.

Someone has broken into the bank's database and deleted every upper case letter from every pattern word. Only the lower case letters are left, and their order is unchanged. Given a PIN and what is left of its pattern word, find the largest number the procedure above could have produced. You may insert upper case letters at any positions of the remaining word, as many as you want, as long as the letter values still sum to the length of the PIN. You cannot reorder the lower case letters.

The input contains a single test case.

The first line contains a PIN of $n$ digits ($6 \le n \le 256$).

The second line contains what is left of the pattern word, $m$ lower case letters ($0 \le m \le n$). This line is empty when $m = 0$.

Print the largest possible sum of the extracted digits. At least one valid pattern word exists.