AT_colopl2018_qual_b すぬけそだて――チュートリアル――

[problemUrl]: https://atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_b あなたは、「すぬけそだて」のチュートリアルをプレイしています。チュートリアルでは、あなたがすぬけ君を拾うに至った経緯が語られます。 始業時刻に遅刻し、昼食をひっくり返し、書いたプログラムはバグだらけ、挙句の果てに先輩を「パパ」と呼んでしまう……失意のどん底に陥っていたあなたは、人気のない暗い路地で、 にゃーにゃーと鳴くか細い声を耳にします。 最初は無視を決め込んでいたあなたでしたが、翌日も、その翌日も、あなたは同じ場所で同じ声を聴くのでした。 気になったあなたは、声のする方向に近づいてみました。草むらの中に広がっていた光景……それには説明の必要はないでしょう。 こうして、あなたとすぬけ君との共同生活が幕を開けたのです！ と、このような心温まるお話を見るのも、もう $ 10 $ 回目です。「すぬけそだて」では、最初にランダムなゲームアイテム「マタタビ」がもらえるのですが、 あなたは好きな「マタタビ」がもらえるまでチュートリアルをやり直すことにした、というのがその理由です。 お話の内容を完全に覚えてしまったあなたは、素早くチュートリアルを終わらせることに集中することにしました。 チュートリアルは、$ N $ 個のフェイズに分かれています。各フェイズは「ローディング」か「ストーリー」のいずれかであり、文字列 $ S $ の $ i $ 文字目が `0` のとき $ i $ 個目の フェイズが「ローディング」であることを、`1` のとき $ i $ 個目のフェイズが「ストーリー」であることを表します。また、$ i $ 個目のフェイズにかかる時間は、最初 $ T_i $ 秒です。 「ストーリー」のフェイズでは、開始直後にスキップボタンを押すことでそのストーリーをちょうど $ X $ 秒で終わらせることができます。スキップボタンを押さない場合、 このストーリーにかかる時間は $ T_i $ 秒のままです。「ローディング」のフェイズでは、進行を速めることはできません。 適切にボタンを押したとき、最小で何秒でチュートリアルを終わらせることができるでしょうか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ S $ $ T_1 $ : $ T_N $

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

### 制約 - $ 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) $ は整数である ### Sample Explanation 1 $ 2 $ 番目のフェイズでスキップを選択し、$ 3 $ 番目のフェイズでスキップを選択しない場合、$ 8+5+3=16 $ 秒でチュートリアルを終わらせることができます。