A. Universal Paperclips
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Universal Paperclips is an incremental game whose goal is to produce paperclips. At your disposal, you have a device that makes paperclips at the click of a button.

For this problem, we'll consider a simplified version of the game with two types of actions:

  1. Click the button. Each click adds a certain amount to the current number of paperclips. This action is denoted by letter "C" ("click").
  2. Upgrade the paperclip-making device. After this action, every subsequence button click will produce one more paperclip. This action is denoted by the letter "U" ("upgrade").

Initially, the player has zero paperclips, and each button click produces one paperclip. An upgrade costs $$$x$$$ paperclips. In all test cases, it's guaranteed that before every upgrade action, the player has at least $$$x$$$ paperclips.

Benny is coding a bot that plays this game. He programmed a fixed sequence of $$$n$$$ actions $$$S$$$, that bot executes cyclically. Every second, the bot makes another action: on the 1st second, the bot executes action $$$S_1$$$, on the 2nd — $$$S_2$$$, ..., on the $$$n$$$-th second it executes $$$S_n$$$, on the $$$n+1$$$-th second — $$$S_1$$$ again, and then the cycle repeats.

How many paperclips will Benny have after his bot runs for $$$t$$$ seconds?

Input

The first line contains three integers $$$n$$$, $$$t$$$ and $$$x$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le t \le 10^9$$$; $$$0 \le x \lt n$$$). The second line contains the string $$$S$$$ of length $$$n$$$, consisting of characters "C" and "U".

Output

Output a single integer — the number of paperclips after $$$t$$$ seconds.

Scoring
SubtaskPointsConstraints
133$$$t \le 10^5$$$
267No additional constraints
Examples
Input
10 15 2
CCCCCUUCCU
Output
25
Input
3 10 0
UUU
Output
0
Input
9 150 1
CCUCCCCUC
Output
2023
Note

Let's go through the first example.

The first five actions produce one paperclip each. Then, the two subsequent upgrades cost two paperclips, so you have only one paperclip left. But, the next two clicks produce three paperclips. The next upgrade costs two paperclips, again. Each one of the last five clicks adds four paperclips.

The final number of paperclips is $$$1 + 1 + 1 + 1 + 1 - 2 - 2 + 3 + 3 - 2 + 4 + 4 + 4 + 4 + 4 = 25$$$.