The Potyczki Algorytmiczne competition has started! Unfortunately, Baltazar cannot neglect his work, and his duties do not magically disappear during the competition week. We can represent Baltazar's day as $n$ segments, each lasting one "byte-hour". The duties during each of these segments belong to one of three categories:

1. office meeting,
2. remote meeting,
3. no duties.

During the day, Baltazar can be at home, at the office, or on the way between them. Baltazar starts and ends his day at home. He can travel to the office at most once, provided he manages to return home before the end of the $n$-th byte-hour. Trips from home to the office and from the office to home take exactly $t$ byte-hours each. Depending on his location, Baltazar can perform different activities:

• At home: Baltazar obviously cannot attend an office meeting, he can (but does not have to) attend a remote meeting, or he can solve problems from the remote rounds of Potyczki Algorytmiczne (but he cannot solve problems while attending a meeting).
• On the way: Baltazar cannot attend any meeting, nor can he solve problems – he must focus on driving (he cannot afford a chauffeur).
• At the office: Baltazar can attend a meeting of any type, and outside of meetings, he must work – he cannot solve problems then.

Your task is to plan Baltazar's day to maximize the number of byte-hours during which he will be solving problems. However, if Baltazar misses more than $k$ meetings, he may be fired from his job. In that case, his participation in next year's edition, like many other life matters, would be in jeopardy – we do not want that.

Baltazar is very well organized, so in each segment, he focuses on exactly one activity; in particular, the routes between home and work take him exactly $t$ full consecutive segments each.

Input

The first line contains three integers $n$, $k$, and $t$ ($3 \le n \le 8000$, $0 \le k \le n$, $1 \le t < \frac{n}{2}$), representing, respectively: the number of segments, the number of meetings Baltazar can miss, and the duration of a one-way trip between Baltazar's home and the office (in byte-hours).

The second line contains a string of length $n$ consisting of characters 1, 2, or 3, representing the type of Baltazar's duties during consecutive segments of the day. The characters correspond to the category numbers given above in the text.

Output

The output should contain a single integer representing the number of byte-hours that Baltazar can spend solving problems without missing more than $k$ meetings. If it is not possible to miss no more than $k$ meetings, output $-1$.

Examples

Input 1

10 1 2
3233313132

Output 1

3

Input 2

7 0 2
3313233

Output 2

0

Input 3

6 5 1
231323

Output 3

6

Input 4

4 1 1
1331

Output 4

-1

Note

Explanation of the examples: In the first example, in one of the optimal solutions, Baltazar spends the consecutive segments of the day as follows:

1. Solving problems
2. Remote meeting from home
3. Solving problems
4. Trip to work
5. Trip to work
6. Office meeting
7. Trip home
8. Trip home (misses one meeting)
9. Solving problems
10. Remote meeting from home

In this plan, Baltazar misses exactly one meeting and solves problems for 3 byte-hours.

In the second example, the only plan in which Baltazar does not lose his job is as follows:

1. Trip to work
2. Trip to work
3. Office meeting
4. Work at the office
5. Remote meeting from the office
6. Trip home
7. Trip home

In the third example, Baltazar can spend the whole day at home, solving problems and skipping all remote meetings.

In the fourth example, Baltazar is unable to attend office meetings because he cannot make it there on time or return home from them on time.