位掩码

题目描述

给定整数 $N$ 和由 0、1、? 组成的字符串 $S$。 设 $T$ 为将 $S$ 中每个 ? 替换为 0 或 1,并把结果解释为二进制整数所能得到的值的集合。 例如,当 $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$

输出格式

输出答案。

样例

?0?
2

1

如题目所述,$T=\lbrace 0,1,4,5\rbrace$。 其中不大于 $N$ 的有 $0$ 和 $1$,应输出其中最大的 $1$。

101
4

-1

有 $T=\lbrace 5\rbrace$,其中不存在不大于 $N$ 的值。

?0?
1000000000000000000

5

数据范围

• $S$ 是由 0、1、? 组成的字符串。
• $S$ 的长度在 $1$ 到 $60$ 之间(含端点)。
• $1 \le N \le 10^{18}$
• $N$ 是整数。