問題文

あなたは、「すぬけそだて」のチュートリアルをプレイしています。チュートリアルでは、あなたがすぬけ君を拾うに至った経緯が語られます。

始業時刻に遅刻し、昼食をひっくり返し、書いたプログラムはバグだらけ、挙句の果てに先輩を「パパ」と呼んでしまう……失意のどん底に陥っていたあなたは、人気のない暗い路地で、 にゃーにゃーと鳴くか細い声を耳にします。

最初は無視を決め込んでいたあなたでしたが、翌日も、その翌日も、あなたは同じ場所で同じ声を聴くのでした。

気になったあなたは、声のする方向に近づいてみました。草むらの中に広がっていた光景……それには説明の必要はないでしょう。

こうして、あなたとすぬけ君との共同生活が幕を開けたのです！

と、このような心温まるお話を見るのも、もう $10$ 回目です。「すぬけそだて」では、最初にランダムなゲームアイテム「マタタビ」がもらえるのですが、 あなたは好きな「マタタビ」がもらえるまでチュートリアルをやり直すことにした、というのがその理由です。

お話の内容を完全に覚えてしまったあなたは、素早くチュートリアルを終わらせることに集中することにしました。

チュートリアルは、$N$ 個のフェイズに分かれています。各フェイズは「ローディング」か「ストーリー」のいずれかであり、文字列 $S$ の $i$ 文字目が 0 のとき $i$ 個目の フェイズが「ローディング」であることを、1 のとき $i$ 個目のフェイズが「ストーリー」であることを表します。また、$i$ 個目のフェイズにかかる時間は、最初 $T_i$ 秒です。

「ストーリー」のフェイズでは、開始直後にスキップボタンを押すことでそのストーリーをちょうど $X$ 秒で終わらせることができます。スキップボタンを押さない場合、 このストーリーにかかる時間は $T_i$ 秒のままです。「ローディング」のフェイズでは、進行を速めることはできません。

適切にボタンを押したとき、最小で何秒でチュートリアルを終わらせることができるでしょうか。

制約

• $1 \\leq N \\leq 1000$
• $1 \\leq X \\leq 10^6$
• $S$ の長さは $N$ である
• $1 \\leq T_i \\leq 10^6(1\\leq i\\leq N)$
• $N,X,T_i(1\\leq i\\leq N)$ は整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $X$ $S$ $T_1$ : $T_N$

出力

チュートリアルを終わらせるために必要な時間の最小値を出力せよ。

入力例 1

3 5
011
8
10
3

出力例 1

16

$2$ 番目のフェイズでスキップを選択し、$3$ 番目のフェイズでスキップを選択しない場合、$8+5+3=16$ 秒でチュートリアルを終わらせることができます。

入力例 2

5 314
10101
159
265
358
979
323

出力例 2

2031