問題文

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

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

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

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

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

と、このような心温まるお話を見るのも、もう 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) は整数である

入力例 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