問題文

岩井星人さんは、コンテスト中の自分の順位を常に気にしています。 そのため、たとえ問題を解いている途中であっても、岩井星人さんは順位表を見ずにはいられません。

大事なことなのでもう一度言います。 岩井星人さんは(順位表を)みずにはいられません。

岩井星人さんは、これからとあるプログラミングコンテストに参加します。 このコンテストでは、参加者に新レート予測値という整数値が設定されており、開始時点での岩井星人さんの新レート予測値は $1200$ です。 なお、このコンテストにおいては、新レート予測値は任意の整数を取り、特に負の値も取りうることに注意してください。

0と1からなる長さ $N$ の文字列 $S'$ が与えられます。 $S'$ を $10^{100}$ 回繰り返した文字列を $S$ とします。

これから、岩井星人さんには $10^{100}$ 個のイベントが順に起こります。 $i$ 個目のイベントは、 $S$の $i$ 文字目によって以下の通りに定まります。

• $S$ の $i$ 文字目が0 の場合

岩井星人さんの新レート予測値が $1$ 減少します。

• $S$ の $i$ 文字目が1 の場合

順位表をみずにはいられない岩井星人さんは、順位表で現在の新レート予測値を確認します。

• 現在の新レート予測値が $1199$ 以下であれば、死に物狂いで問題を解き、ACを得ます。その結果、岩井星人さんの新レート予測値は $1$ 増加します。
• 現在の新レート予測値が $1200$ 以上であれば、「サーバー代がもったいない！」と叫ぶだけで、何もしません。 岩井星人さんの新レート予測値に変化はありません。

順位表をみずにはいられない岩井星人さんが $A$ 個目のACを得るのは、何個目のイベントが起こったときでしょう？

ただし、コンテストの問題数は十分に多く、岩井星人さんがすべての問題を解ききることはないものとします。また、制約から、答えは $2 \times 10^{18}$ 以下の整数であることが保証されます。

制約

• $2 \le N \le 2 \times 10^5$
• $1 \le A \le 10^{12}$
• $S'$ は 0と1からなる文字列
• $|S'|=N$
• $S'$ は 0と1がそれぞれ少なくとも $1$ つずつ含まれる
• $N,A$ は整数

入力

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

$N\ A$
$S'$

出力

答えを出力せよ。

サンプル

5 3
10100

8

7 1
1000001

7

2 20
10

41

10 81181819
1011010011

202954549