Puju

Interview

Time limit1sMemory limit1024 MB

Summary

Given a row of N cells with thickets, find the largest plot Kazimir can reach after clearing thickets on a walk from S that uses at most K steps.

Level: Medium5 of 10
Topics: Two pointers, Prefix sum, Greedy
Solved: No attempts yet

Statement

Aednik Kazimir recently bought a new plot of land made of $N$ cells in a row. The cells are numbered $1$ to $N$ from left to right. Unfortunately, some cells are overgrown with puju thickets, so they are not suitable for gardening. To clear them, Kazimir rented a weeding tractor.

At the start, Kazimir is on cell $S$ with the tractor. In each step he can move from his current cell to one of its neighbors, cell $i - 1$ or cell $i + 1$ . If the new cell has thickets, the tractor uproots them and the cell becomes suitable for gardening. The tractor has fuel for only $K$ steps.

After the weeding, Kazimir can move without limit between cells free of thickets and plant anywhere he likes, but he cannot pass through cells with thickets. Find the maximum area where Kazimir can grow plants.

Input

The first line contains the plot size $N$ ( $1 \le N \le 10^6$ ), the tractor fuel $K$ ( $0 \le K \le 10^9$ ), and Kazimir's starting cell $S$ ( $1 \le S \le N$ ).

The second line contains exactly $N$ characters. '.' marks a cell without thickets and '#' marks a cell with thickets. Cell $S$ is suitable for gardening.

Output

Print the maximum number of cells where Kazimir can start growing plants.

Examples5

Example 1
Input
```
10 1 1
.#........
```
Expected output
```
10
```
Example 2
Input
```
10 1 3
.#.#......
```
Expected output
```
8
```
Example 3
Input
```
10 2 3
.#.#......
```
Expected output
```
8
```
Example 4
Input
```
10 3 3
.#.#......
```
Expected output
```
10
```
Example 5
Input
```
10 5 1
.#########
```
Expected output
```
6
```