Potyczki Algorytmiczneが開幕しました！残念ながら、Bajtazarは仕事を疎かにすることはできず、競技プログラミングの週であっても彼の義務が魔法のように消えることはありません。Bajtazarの一日は、$n$ 個のセグメントに分けることができ、各セグメントは1バイト時間（bajtogodzina）続きます。各セグメントにおける義務は、以下の3つのカテゴリのいずれかに属します。

1. オフィスでの会議
2. リモート会議
3. 義務なし

一日の間、Bajtazarは自宅、オフィス、またはその間の移動中にいることができます。Bajtazarは自宅で一日を開始し、終了します。彼は、$n$ 番目のバイト時間が終わる前に自宅に戻れる場合に限り、最大で1回だけオフィスへ行くことができます。自宅からオフィスへの移動、およびオフィスから自宅への移動には、それぞれ正確に $t$ バイト時間かかります。Bajtazarは現在地に応じて、異なる行動をとることができます。

• 自宅：Bajtazarは当然オフィスでの会議には参加できません。リモート会議に参加する（参加しなくてもよい）か、Potyczki Algorytmiczneの遠隔ラウンドの課題を解くことができます（ただし、会議に参加しながら課題を解くことはできません）。
• 移動中：Bajtazarは会議に参加することも、課題を解くこともできません。運転に集中しなければなりません（運転手を雇う余裕はありません）。
• オフィス：Bajtazarはあらゆる種類の会議に参加できます。会議以外の時間は働かなければならず、その間は課題を解くことができません。

あなたのタスクは、Bajtazarが課題を解くバイト時間の合計を最大化するように、彼の一日を計画することです。ただし、Bajtazarが $k$ 回を超える会議を欠席した場合、彼は解雇される可能性があります。そうなれば、他の多くの人生の事柄と同様に、来年の大会への参加も危うくなってしまいます。私たちはそれを望んでいません。

Bajtazarは非常に計画的であるため、各セグメントで正確に一つの活動に集中します。特に、自宅と職場の間の移動には、それぞれ正確に $t$ 個の連続したセグメントを要します。

入力

1行目には、3つの整数 $n, k, t$ ($3 \le n \le 8000, 0 \le k \le n, 1 \le t < \frac{n}{2}$) が与えられます。これらはそれぞれ、セグメント数、Bajtazarが欠席してもよい会議の数、および自宅とオフィス間の片道移動時間（バイト時間単位）を表します。

2行目には、長さ $n$ の文字列が与えられます。これは、一日の各セグメントにおけるBajtazarの義務の種類を表す '1', '2', '3' からなる文字列です。各文字は、上記で説明したカテゴリ番号に対応しています。

出力

$k$ 回以下の会議欠席で、Bajtazarが課題を解くことに費やせるバイト時間の最大値を表す整数を1つ出力してください。もし $k$ 回以下の欠席で一日を終えることが不可能な場合は、$-1$ を出力してください。

入出力例

入力 1

10 1 2
3233313132

出力 1

3

入力 2

7 0 2
3313233

出力 2

0

入力 3

6 5 1
231323

出力 3

6

入力 4

4 1 1
1331

出力 4

-1

注記

例の解説：最初の例において、最適な解決策の一つでは、Bajtazarは一日を以下のように過ごします。

1. 課題を解く
2. 自宅でリモート会議
3. 課題を解く
4. オフィスへ移動
5. オフィスへ移動
6. オフィスで会議
7. 自宅へ移動
8. 自宅へ移動（会議を1回欠席）
9. 課題を解く
10. 自宅でリモート会議

この計画では、Bajtazarはちょうど1回の会議を欠席し、3バイト時間の間課題を解いています。

2番目の例では、Bajtazarが解雇されない唯一の計画は以下の通りです。

1. オフィスへ移動
2. オフィスへ移動
3. オフィスで会議
4. オフィスで仕事
5. オフィスからリモート会議
6. 自宅へ移動
7. 自宅へ移動

3番目の例では、Bajtazarは一日中自宅にいて、すべてのリモート会議を欠席しながら課題を解くことができます。

4番目の例では、Bajtazarはオフィスでの会議に間に合うように移動したり、そこから自宅へ戻ったりすることができないため、会議に参加することができません。