Fractal Expansion#13044
Sign in

Fractal Expansion

2 seconds
256 megabytes
Hard

You are given a string consisting only of the characters A and B, and an integer .

For a string , define by replacing each character independently as follows:

Initially, the current string is empty. You can perform the following operations:

  1. Append the next character of to the current string. If its length becomes , the cost of this operation is .

  2. If the current string is a non-empty string , replace it with

    s+f(s).

    The cost of this operation is . It can be performed only if the resulting string is a prefix of .

Find the minimum total cost needed to obtain .

Input

The first line contains one integer (1 \le n \le 2 \cdot 10^5).

The second line contains the string of length , consisting only of the characters A and B.

The third line contains one integer (1 \le c \le 10^9).

Output

Print one integer — the minimum total cost needed to obtain .

Examples

Example 1

Loading
Loading

Note

In the example, first append A. The cost of this operation is .

Now the current string is A. Since

f(\texttt{A})=\texttt{AB},

we can perform the second operation and obtain

\texttt{A}+\texttt{AB}=\texttt{AAB}.

This operation costs , so the total cost is

1+3=4.

Scoring

  1. Subtask ( points): n \le 20.

  2. Subtask ( points): n \le 100.

  3. Subtask ( points): n \le 2000.

  4. Subtask ( points): c = 1.

  5. Subtask ( points): No additional constraints.