Problem Statement

You are given a string S of length N over lowercase letters, you may delete any characters from S (each deletion costs D ). After deletions, the string is run-length encoded : each maximal run of the same character c of length L is encoded as: cL (length ⌊log 10 L⌋ + 2 if L > 1 ), c (length 1 if L = 1 ). The compression score is: N_original - encoded_length - deletion_cost . Find the maximum total compression score . Input Format The first line contains a string, s , denoting the input string of length N (lowercase letters). The second line contains a integer, d , denoting the cost per character deleted. Constraints 1 ≤ | s | ≤ 100 1 ≤ d ≤ 20 Sample Test Cases Case 1 Input: aabbaa 1 Output: 2 Explanation: N=6, D=1. If we do not delete anything, the string is encoded as "a2b2a2", which has a length of 6. The score would be 6-6-0=0. However, if we delete the two 'b's, the deletion cost is 2x1=2. The remaining string is "aaaa", which is encoded as "a4", with a length of 2.