The robot moves on the field, consisting of \textbf{N} cells arranged in a row. At each cell is the cube of a certain color. At the beginning of the robot is in the first field of the cell and not keeping a single cube. Being in a cage, the robot can perform no more than once each of the following: (1) to put the cube of the same color, which lies in the current cell (2) to raise with the cells that block, which was in her first. After that, the robot moves to the next cell, or stops if the current cell is the last on the field. Simultaneously, the robot can hold no more than \textbf{K} blocks. At the time of stopping the robot does not have to keep a single cube. Write a program that according to the color blocks and limiting the number of cubes, which can keep the robot determines the total maximum number of blocks that the robot can move from place to place, moving on to the field. \InputFile The first line contains a string of length \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000}). Line consists of a small Latin letters. Each letter corresponds to a cell field and determines the color of the cube, which is located in the cell. The second line contains restrictions on the number of cubes that can simultaneously keep the robot \textbf{K }(\textbf{1 }≤ \textbf{K }≤ \textbf{25}). \OutputFile The only line in the output file should contain an integer - maximum number of blocks, the location where the robot can change moving through the field.