Closing Ceremony

Interview

Time limit1sMemory limit1024 MB

Summary

Given a row of up to 30 seats labeled A to D, find the maximum number of adjacent equal-group pairs after each person swaps at most once with someone within K seats.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Brute force, Implementation
Solved: No attempts yet

Problem

Several groups are invited to sit in the front row at the closing ceremony of this year's IOI (International Olympiad in Informatics). Each person has been assigned a seat. Since the IOI organizers did not realize that the groups would like to sit together, they handed out the seats somewhat haphazardly. The people therefore decide to take matters into their own hands: by swapping seats with each other, they try to maximize the number of pairs of people from the same group who sit next to each other. The organizers get angry if the seat swapping becomes too messy, so they decide that each person may swap seats at most once, and then only with a person sitting at most $K$ seats away.

What is the largest number of pairs of people from the same group sitting next to each other that can be achieved?

Input

The first line contains a string of length $1 \leq N \leq 30$ describing the original row. Each letter in the string describes which group the person in the corresponding seat belongs to, and is one of A, B, C, or D. The second line contains an integer $K$ , the maximum distance a person may move ( $1 \leq K \leq 2$ ).

Output

Print a single integer: the largest number of pairs of people from the same group sitting next to each other that can be achieved through valid seat swaps.

Hint

In sample 1, the following arrangement can be achieved: A B B A A A, by swapping the first and second persons, and swapping the third and fourth persons.

In sample 2, the following arrangement can be achieved: A A C C B B B A, by swapping the second and third persons, and swapping the fourth and sixth persons.

Examples2

Example 1
Input
```
BAABAA
1
```
Expected output
```
3
```
Example 2
Input
```
ACABBCBA
2
```
Expected output
```
4
```