There are $n$ consecutive seat places in a railway carriage. Each place is either empty or occupied by a passenger.
The university team for the Olympiad consists of $a$ student-programmers and $b$ student-athletes. Determine the largest number of students from all $a+b$ students, which you can put in the railway carriage so that:
* no student-programmer is sitting next to the student-programmer;
* and no student-athlete is sitting next to the student-athlete.
In the other words, there should not be two consecutive (adjacent) places where two student-athletes or two student-programmers are sitting.
Consider that initially occupied seat places are occupied by jury members (who obviously are not students at all).
## Input
The first line contain three integers $n$, $a$ and $b$ ($1 \le n \le 2\cdot10^{5}$, $0 \le a, b \le 2\cdot10^{5}$, $a + b > 0$) — total number of seat places in the railway carriage, the number of student-programmers and the number of student-athletes.
The second line contains a string with length $n$, consisting of characters "_._" and "_*_". The dot means that the corresponding place is empty. The asterisk means that the corresponding place is occupied by the jury member.
## Output
Print the largest number of students, which you can put in the railway carriage so that no student-programmer is sitting next to a student-programmer and no student-athlete is sitting next to a student-athlete.
[samples]
## Note
In the first example you can put all student, for example, in the following way: _*.AB*_
In the second example you can put four students, for example, in the following way: _*BAB*B_
In the third example you can put seven students, for example, in the following way: _B*ABAB**A*B_
The letter _A_ means a student-programmer, and the letter _B_ — student-athlete.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of consecutive seats.
Let $ a, b \in \mathbb{Z}_{\geq 0} $ be the number of student-programmers and student-athletes, respectively, with $ a + b > 0 $.
Let $ S \in \{ \text{.}, \text{*} \}^n $ be a string representing seat occupancy:
- $ \text{.} $ denotes an empty seat (available for students),
- $ \text{*} $ denotes an occupied seat (by jury, unavailable).
Let $ I \subseteq \{1, 2, \dots, n\} $ be the set of indices where seats are available (i.e., $ S_i = \text{.} $).
Let $ m = |I| $ be the number of available seats.
**Constraints**
1. $ 1 \leq n \leq 2 \cdot 10^5 $
2. $ 0 \leq a, b \leq 2 \cdot 10^5 $, $ a + b > 0 $
3. The available seats form contiguous or non-contiguous segments; adjacency is defined by consecutive indices in $ \{1, \dots, n\} $.
**Objective**
Maximize the total number of students $ x = x_a + x_b $ placed on available seats, where:
- $ x_a \leq a $, $ x_b \leq b $,
- No two adjacent available seats are assigned to two student-programmers,
- No two adjacent available seats are assigned to two student-athletes.
Equivalently, the assignment to adjacent available seats must alternate between programmer (A) and athlete (B).
**Key Insight**
The problem reduces to:
- Partition the available seats into maximal contiguous blocks of consecutive `.`.
- For each contiguous block of length $ L $, the maximum number of students that can be placed is $ L $, under the alternating constraint.
- The maximum number of A’s and B’s in a block of length $ L $ is:
$$
\left\lceil \frac{L}{2} \right\rceil \text{ of one type}, \quad \left\lfloor \frac{L}{2} \right\rfloor \text{ of the other}
$$
(and we can choose which type starts).
- Thus, over all blocks, the total maximum possible A’s and B’s are bounded by:
$$
A_{\max} = \sum_{\text{blocks}} \left\lceil \frac{L_i}{2} \right\rceil, \quad
B_{\max} = \sum_{\text{blocks}} \left\lfloor \frac{L_i}{2} \right\rfloor
$$
(or vice versa, since we can flip the assignment per block).
- The optimal total is:
$$
\min(a + b,\; m,\; \max_{\text{assignments}} (x_a + x_b))
$$
where $ x_a \leq \min(a, A_{\max} + B_{\max} - B_{\min}) $, etc. — but more simply:
**Final Formulation**
Let $ \text{blocks} = \{L_1, L_2, \dots, L_k\} $ be the lengths of maximal contiguous available seat segments.
Define:
$$
A_{\text{total}} = \sum_{i=1}^k \left\lceil \frac{L_i}{2} \right\rceil, \quad
B_{\text{total}} = \sum_{i=1}^k \left\lfloor \frac{L_i}{2} \right\rfloor
$$
Then the maximum number of students that can be seated is:
$$
\min(a + b,\; m,\; \min(a, A_{\text{total}}) + \min(b, B_{\text{total}}))
$$
**But wait**: since we can *choose* for each block whether to start with A or B, the optimal is:
$$
\min(a + b,\; m,\; \min(a + b,\; A_{\text{total}} + B_{\text{total}}),\; \max_{x_a + x_b} \{ x_a \leq a, x_b \leq b, x_a \leq A_{\text{total}}, x_b \leq B_{\text{total}}, x_a + x_b \leq m \})
$$
Actually, since $ A_{\text{total}} + B_{\text{total}} = m $, and we can assign optimally per block (i.e., assign more A’s to blocks where we need them), the maximum number of students is:
$$
\min(a + b,\; m,\; \min(a, A_{\text{total}}) + \min(b, B_{\text{total}}))
$$
is **incorrect** because we can swap A/B per block.
The correct and known optimal approach is:
Let $ T = \sum_{i=1}^k \left\lfloor \frac{L_i}{2} \right\rfloor $, and $ R = \sum_{i=1}^k (L_i \bmod 2) $ (number of blocks with odd length).
Then, maximum A’s we can place is $ T + R $, maximum B’s is $ T $, or vice versa.
So total possible under alternating constraint is $ T + R = m $, and we can distribute up to $ T + R $ of one type and $ T $ of the other.
Thus, the maximum number of students we can place is:
$$
\min(a + b,\; m,\; \min(a, T + R) + \min(b, T)) \quad \text{or} \quad \min(a + b,\; m,\; \min(a, T) + \min(b, T + R))
$$
So the maximum is:
$$
\min(a + b,\; m,\; \min(a, T + R) + \min(b, T),\; \min(a, T) + \min(b, T + R))
$$
But since $ \min(a, T + R) + \min(b, T) \geq \min(a, T) + \min(b, T + R) $ is not guaranteed, we take the **maximum** of the two assignments:
$$
\boxed{
\min\left(a + b,\; m,\; \max\left( \min(a, T + R) + \min(b, T),\; \min(a, T) + \min(b, T + R) \right) \right)
}
$$
Where:
- $ m = $ number of available seats (dots),
- $ T = \sum_{i} \left\lfloor \frac{L_i}{2} \right\rfloor $,
- $ R = $ number of blocks with odd length $ L_i $,
- $ T + R = \sum_{i} \left\lceil \frac{L_i}{2} \right\rceil $.
This is the formal mathematical formulation.