Given a string consisting only of uppercase letters A–Z. Your task is to compress this string using a two-stage compression scheme.
First, replace every maximal run of the same letter X of length n with the token Xn, e.g.:
AAABBBBZ -> A3B4Z1
QWWEEERRRRTTTTTYYYYYY -> Q1W2E3R4T5Y6
X -> X1
In the second step, some Xn runs can be replaced with lowercase letters. More precisely, the compression algorithm can use the 26 lowercase letters to replace some Xn tokens. One lowercase letter can map to at most one token of form Xn. If replacements occur, the algorithm attaches a header at the front of the compressed stream indicating which Xn tokens are replaced followed by two semicolons. The order of the tokens in the header also establishes their mapping to the lowercase letters in increasing order. The header may look like this: A3B1S7;;, which means the token A3 is replaced with a, the token B1 is replaced with b and the token S7 is replaced with c.
The following examples illustrate possible replacements:
X1
-> X1 (no replacements)
-> X1;;a
A1000Z2
-> A1000Z2;;ab
A3B2S10A3S10A3S10
-> S10;;A3B2aA3aA3a
-> A3B2S10;;abcacac
Your input consists of line separated strings, each consisting only of uppercase letters A-Z. You need to compress each line with the above algorithm in such a way that the compressed stream is as short as possible. The final output for a line is then the product of the shortest compressed stream length and the line index (starting at 1).
Input format
Each line in the input consists of a string using only uppercase characters A-Z.
Output format
The sum of the products of the shortest possible compression lengths and the line indices (starting at 1) for each string in the input.
Sample input
A
BBCCBBCCBBCCBBCC
Sample output
30