Maximizing Problem Solving Time

Bajtazar has a day divided into n time segments. In each segment, one of three events occurs:

• Offline meeting
• Online meeting
• Free time

At the beginning of the day (segment 1) Bajtazar is at home and at the end of the day (after segment n) he must be at home. His location in any segment can be:

• Home:
  • If an offline meeting is scheduled, he cannot attend it (i.e. he is forced to skip it).
  • If an online meeting is scheduled, he may choose either to attend (and spend the segment in the meeting) or to skip it and solve problems instead.
  • In free time he can solve problems.
• Company:
  • He must attend both offline and online meetings.
  • He cannot solve problems even if the segment is free.
• Commuting:
  • Whether a meeting is scheduled or not, he cannot attend it, and he cannot solve problems.

Bajtazar is allowed to skip at most k meetings. When he skips a meeting at home (either a forced skip for an offline meeting or a voluntary skip for an online meeting), it counts towards that limit.

Moreover, Bajtazar may opt to visit his office at most once. The transition is as follows:

• He can choose to start commuting from home to the company. Commuting takes t consecutive segments. That is, if he starts commuting at the beginning of segment i, he finishes commuting at the end of segment i+t-1 and will be at the company at segment i+t.
• Similarly, once at the company, he can choose to commute back to home (also taking t segments).

At home, when a meeting is scheduled, he has the following options:

• If the event is free, he can solve problems and earn 1 unit of practice time with no cost.
• If the event is an online meeting, he may either attend (earning 0 units) or skip it (earning 1 unit, but costing 1 skip).
• If the event is an offline meeting, he is forced to skip it and therefore earns 1 unit at the cost of 1 skip.

At the company or while commuting, he earns 0 units regardless of the event, but note that while at company he must attend meetings (so no skip cost is incurred) and while commuting the time is unproductive.

Your task is to compute the maximum number of segments during which Bajtazar can solve problems, given that he can skip at most k meetings. The input is given as follows:

n t k
a1 a2 ... an

Here, each a_i is an integer where:

• 1 represents an offline meeting
• 2 represents an online meeting
• 3 represents free time

Note: Bajtazar may choose to start commuting at the beginning of a segment instead of processing that segment at his current location. Commuting takes exactly t segments, and he cannot perform any productive activity during commuting. Also, he can only visit the company at most once (which means he can commute from home to company and then later from company back to home, and no further office visit is allowed).

inputFormat

The first line contains three integers n, t, and k (1 ≤ n, t, k ≤ some limits) — the number of time segments, the number of segments needed for commuting, and the maximum number of meetings Bajtazar can skip.

The second line contains n integers a₁, a₂, ..., a_n. Each a_i is one of {1, 2, 3} representing an offline meeting, an online meeting, or free time respectively.

outputFormat

Output a single integer — the maximum number of segments in which Bajtazar can solve problems.

sample

5 1 1
3 2 1 3 3

4

</p>