题目描述

给定一个由 0、1、? 组成的字符串 $S$ 和一个整数 $N$。将 $S$ 中的每个 ? 替换为 0 或 1，并将其视为二进制整数，得到的所有可能值的集合记为 $T$。例如，当 $S=$ ?0? 时，$T=\lbrace 000\_{(2)},001\_{(2)},100\_{(2)},101\_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace$。

请输出 $T$ 中不超过 $N$ 的最大值（以十进制整数形式输出）。如果 $T$ 中没有不超过 $N$ 的值，则输出 -1。

输入格式

输入以以下格式从标准输入读入。

$S$ $N$

输出格式

请输出答案。

样例 1

输入

?0?
2

输出

1

样例 2

输入

101
4

输出

-1

样例 3

输入

?0?
1000000000000000000

输出

5

说明/提示

限制条件

• $S$ 由 0、1、? 组成。
• $S$ 的长度为 $1$ 到 $60$。
• $1 \leq N \leq 10^{18}$。
• $N$ 是整数。

样例解释 1

如题目中所示，$T=\lbrace 0,1,4,5\rbrace$。$T$ 中不超过 $N$ 的值为 $0$ 和 $1$，其中最大的是 $1$，因此输出 $1$。

样例解释 2

$T=\lbrace 5\rbrace$，因此 $T$ 中没有不超过 $N$ 的值。

由 ChatGPT 4.1 翻译