Maximizing Excellence by Swapping Temporary Persons

There are n persons sitting in a row (indexed from 1 to n). Each person is of one of four types:

1. Constant Positive (type 1): Always in the positive (engaged) state.
2. Constant Negative (type 2): Always in the negative (slumping) state.
3. Temporary Positive (type 3): Their state may change over time. Their update rule is: if at some second a type-3 person is positive but both immediate neighbors are negative, then next second it becomes negative; if it is negative and at least one neighbor is positive then it becomes positive. In short: if any neighbor is positive, then become positive.
4. Temporary Negative (type 4): Their update rule is the reverse. If at some second a type-4 person is negative but both neighbors are positive then it becomes positive; if it is positive and at least one neighbor is negative then it becomes negative. In short: if any neighbor is negative, then become negative.

The constant persons (types 1 and 2) never change state. Among the constant persons it is guaranteed that they appear alternately (i.e. no two constant persons of the same type are adjacent in the row when considering only constant persons).

A state configuration is an assignment of a state (positive or negative) to every person. A configuration is stable if no one will update in the next second. For the temporary persons, when they are positive, we call them positive temporary and when negative, negative temporary. (Recall that constant persons are always positive for type 1 and negative for type 2.)

The score of a configuration is defined as the number of persons in the positive state (i.e. constant positives plus temporary persons if they are positive).

The best configuration is a stable configuration having the maximum score among all possible stable configurations. Its score is called the excellent degree of the row. Although the dynamics are deterministic, you are allowed to set the initial state arbitrarily for every temporary person so that the system reaches any stable configuration you desire.

Since the constant persons are locked (type 1 and type 2) the only way to affect the final configuration is by swapping the positions of the temporary persons (types 3 and 4). You are allowed to swap at most k pairs of temporary persons (each swap exchanges two temporary persons in different positions). After swapping, you can set the initial states arbitrarily so that the system reaches the best stable configuration possible under that arrangement.

Your task is to maximize the excellent degree. It can be shown that under any arrangement the optimal stable configuration will have all constant persons (type 1) and all temporary persons in the interior positive except that at a boundary between a positive constant and a negative constant the temporary person adjoining the negative constant may be forced to be negative if it is of type 4. In particular, if a segment (a contiguous block of temporary persons between two constant persons) has boundaries (positive, negative), then if the last temporary person in this segment is of type 4 it cannot be positive in a stable configuration. Similarly, if the boundaries are (negative, positive), then the first temporary person in that segment must be negative if it is of type 4. Fortunately, by swapping you can fix some of these "penalties". Each swap (of a pair of temporary persons) can fix at most one such boundary issue. Let P be the total number of forced negatives at boundaries (penalties) in the original arrangement. By swapping at most k pairs you can fix at most k penalties. Therefore, the maximum excellent degree that can be achieved is:

$$\text{excellent degree} = \text{(\# of constant positives)} + \text{(\# of temporary persons)} - \max(P - k, 0). $$

The input guarantees that the first and last persons are constant (i.e. type 1 or type 2). Use the information of the row to compute the maximum excellent degree after performing at most k swaps among temporary persons.

inputFormat

The first line contains two integers n and k (2 \le n \le 10^5, 0 \le k \le 10^5), where n is the total number of persons and k is the maximum number of pairs of temporary persons you can swap.

The second line contains n integers a₁, a₂, ..., a_n (ai \in \{1,2,3,4\}), representing the type of each person. It is guaranteed that a₁ and a_n are in \(\{1,2\}\) (i.e. constant persons) and that when considering only constant persons, types alternate.

outputFormat

Output a single integer – the maximum excellent degree (i.e. the largest number of persons that can be in the positive state in a stable configuration) achievable after at most k swaps.

Note: You may assume that after swapping, you can set the initial states arbitrarily (for temporary persons) so as to achieve a stable configuration that realizes the maximum possible score.

sample

5 0
1 3 4 3 2

4