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