A binary string is a non-empty sequence of $0$'s and $1$'s, e.g., _010110_, _1_, _11101_, etc. Ayu has a favorite binary string $S$ which contains no leading zeroes. She wants to convert $S$ into its *decimal* representation with her calculator.
Unfortunately, her calculator cannot work on any integer larger than $K$ and it will crash. Therefore, Ayu may need to remove zero or more bits from $S$ while maintaining the order of the remaining bits such that its decimal representation is no larger than $K$. The resulting binary string also must not contain any leading zeroes.
Your task is to help Ayu to determine the minimum number of bits to be removed from $S$ to satisfy Ayu's need.
For example, let $S$ = _1100101_ and $K = 13$. Note that _1100101_ is $101$ in decimal representation, thus, we need to remove several bits from $S$ to make it no larger than $K$. We can remove the $3^(r d)$, $5^(t h)$, and $6^(t h)$ most significant bits, i.e. _1100101_ $arrow.r$ _1101_. The decimal representation of _1101_ is $13$, which is no larger than $K = 13$. In this example, we removed $3$ bits, and this is the minimum possible (If we remove only $2$ bits, then we will have a binary string of length $5$ bits; notice that any binary string of length $5$ bits has a value of at least $16$ in decimal representation).
Input begins with a line containing an integer $K$ ($1 <= K <= 2^(60)$) representing the limit of Ayu's calculator. The second line contains a binary string $S$ ($1 <= | S | <= 60$) representing Ayu's favorite binary string. You may safely assume $S$ contains no leading zeroes.
Output contains an integer in a line representing the minimum number of bits to be removed from $S$.
_Explanation for the sample input/output #1_
This sample is illustrated by the example given in the problem description above.
_Explanation for the sample input/output #2_
Ayu must remove $4$ bits to get _111_, which is $7$ in its decimal representation.
## Input
Input begins with a line containing an integer $K$ ($1 <= K <= 2^(60)$) representing the limit of Ayu's calculator. The second line contains a binary string $S$ ($1 <= | S | <= 60$) representing Ayu's favorite binary string. You may safely assume $S$ contains no leading zeroes.
## Output
Output contains an integer in a line representing the minimum number of bits to be removed from $S$.
[samples]
## Note
_Explanation for the sample input/output #1_This sample is illustrated by the example given in the problem description above._Explanation for the sample input/output #2_Ayu must remove $4$ bits to get _111_, which is $7$ in its decimal representation.
编程训练营将在伯兰举行。参赛者将在一栋两层楼的建筑中进行比赛。每层楼将排列一排 $n$ 张桌子。每层楼的桌子从左到右编号，从 1 开始。有一部楼梯允许参赛者在两层之间通行。建筑的结构如下图所示：
对于每张桌子，已知是否会有队伍在此桌工作。
组织者决定安装一台打印机，以便参赛者打印他们的解决方案。为此，他们必须选择一层楼放置打印机，并在该层选择一张桌子。打印机可以安装在任意一张桌子上（可以是空桌，也可以是某个队伍将使用的桌子）。
我们定义每个队伍的不便值。例如，队伍 $i$ 将坐在楼层 $f_i$ 的桌子 $a_i$ 上，而打印机安装在楼层 $f_p$ 的桌子 $a_p$ 上。如果打印机安装在队伍 $i$ 所在的同一层（即 $f_i = f_p$），则队伍 $i$ 的不便值为 $| a_i - a_p |$。如果打印机安装在另一层（即 $f_i \ne f_p$），则队伍 $i$ 的不便值为 $a_i + k + a_p$：队伍需先走到其所在房间的出口（对应 $a_i$），然后通过楼梯到达另一层（对应 $k$），再走到打印机所在的桌子（对应 $a_p$）。
组织者希望放置打印机，使得所有队伍中的最大不便值最小化。你的任务是帮助他们：告知他们打印机应放置在哪一层、哪一张桌子。
第一行包含两个整数 $n$ 和 $k$ $(1 \le n \le 1\,000, 1 \le k \le 1\,000)$ —— 每层楼的桌子数量，以及通过楼梯到达另一层所需的时间。
第二行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1。该字符串对应第二层桌子上的队伍分布：如果第 $i$ 个字符是 1，则第二层第 $i$ 张桌子将有队伍；否则该桌子为空。
第三行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1。该字符串对应第一层桌子上的队伍分布：如果第 $i$ 个字符是 1，则第一层第 $i$ 张桌子将有队伍；否则该桌子为空。
保证至少有一个队伍参加训练营（即这两个字符串中至少有一个字符是 1）。
第一行应输出一个整数 —— 所有队伍中可能的最小最大不便值。
第二行应输出两个整数 —— 打印机应放置的楼层编号和桌子编号。如果有多个最优解，输出任意一个即可。
在第一个示例中，可以将打印机放置在第一层第 1 张桌子。此时，第二层队伍的不便值为 $3 + 2 + 1 = 6$，第一层队伍的不便值为 $| 1 - 3 | = 2$。因此最小可能的最大不便值为 $6$。
## Input
第一行包含两个整数 $n$ 和 $k$ $(1 \le n \le 1\,000, 1 \le k \le 1\,000)$ —— 每层楼的桌子数量，以及通过楼梯到达另一层所需的时间。第二行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1。该字符串对应第二层桌子上的队伍分布：如果第 $i$ 个字符是 1，则第二层第 $i$ 张桌子将有队伍；否则该桌子为空。第三行包含一个长度为 $n$ 的字符串，每个字符为 0 或 1。该字符串对应第一层桌子上的队伍分布：如果第 $i$ 个字符是 1，则第一层第 $i$ 张桌子将有队伍；否则该桌子为空。保证至少有一个队伍参加训练营（即这两个字符串中至少有一个字符是 1）。
## Output
第一行应输出一个整数 —— 所有队伍中可能的最小最大不便值。第二行应输出两个整数 —— 打印机应放置的楼层编号和桌子编号。如果有多个最优解，输出任意一个即可。
[samples]
## Note
在第一个示例中，可以将打印机放置在第一层第 1 张桌子。此时，第二层队伍的不便值为 $3 + 2 + 1 = 6$，第一层队伍的不便值为 $| 1 - 3 | = 2$。因此最小可能的最大不便值为 $6$。
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $ be the number of tables per floor and the staircase cost, respectively.
Let $ S_2 \in \{0,1\}^n $ be the binary string representing occupied tables on the **second** floor: $ S_2[i] = 1 $ iff a team sits at table $ i+1 $ on floor 2.
Let $ S_1 \in \{0,1\}^n $ be the binary string representing occupied tables on the **first** floor: $ S_1[i] = 1 $ iff a team sits at table $ i+1 $ on floor 1.
Let $ T_1 = \{ i \in \{1, \dots, n\} \mid S_1[i-1] = 1 \} $ be the set of table indices on floor 1 with teams.
Let $ T_2 = \{ i \in \{1, \dots, n\} \mid S_2[i-1] = 1 \} $ be the set of table indices on floor 2 with teams.
Let $ T = T_1 \cup T_2 $ be the set of all teams.
Let $ p \in \{1,2\} \times \{1, \dots, n\} $ be the printer placement: $ p = (f_p, a_p) $, where $ f_p \in \{1,2\} $ is the floor, $ a_p \in \{1, \dots, n\} $ is the table.
**Inconvenience Function**
For a team at $ (f_i, a_i) \in T $, the inconvenience to printer at $ (f_p, a_p) $ is:
$$
d((f_i, a_i), (f_p, a_p)) =
\begin{cases}
|a_i - a_p| & \text{if } f_i = f_p \\
a_i + k + a_p & \text{if } f_i \ne f_p
\end{cases}
$$
**Objective**
Find $ p^* = (f_p^*, a_p^*) \in \{1,2\} \times \{1, \dots, n\} $ minimizing:
$$
\max_{(f_i, a_i) \in T} d((f_i, a_i), (f_p^*, a_p^*))
$$
Output the minimal maximum inconvenience and any optimal $ p^* $.