SuSu's Power

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

SuSu wants to become powerful to protect his friends, so he does practices every day.

There are two kinds of practice in a day:

  • A : SuSu's power will be increased by d. (d ∈ {-1, 1})
  • B : SuSu changes the sign of d. (d = -d)

SuSu has already made a n days' plan about how to practice, but the plan is not very well.

So you have to change m times for the plan(one day's plan can be changed several times), so that SuSu can get much more power.

Initially, SuSu's power is 0, and the value of d is 1.

Please notice that the negative power is also very important for SuSu, just make the absolute value as max as possible.

Input

There are multiple cases.

For each case:

The first line is an integer n(1 ≤ n ≤ 100), the number of days SuSu has to do practices.

The second line is a string whose length is n, the ith character means what kind of practice SuSu planned to do on the ith day, then followed by an integer m(1 ≤ m ≤ 50).

Output

For each case, output one line containing "Case #x: " followed by the maximum of the power's absolute value SuSu can get.

Sample Input

7
AAABAAA 2
2
AB 1

Sample Output

Case #1: 6
Case #2: 2

Hint

In the first example you have to change two day. One of the ways to get 6 power is to change the fourth day and first or last one.

In the second example the best option is to change the second day "B" to "A" — this way SuSu will get 2 power.

Source

KIDx

Manager

Information
Solved Number63
Submit Number192
Problem Tags
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel