问题描述

给定一个整数$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$是一个由0、1和?组成的字符串。
• $S$的长度在$1$到$60$之间，包括边界值。
• $1\leq N \leq 10^{18}$
• $N$是一个整数。

输入

输入以以下格式从标准输入中给出：

$S$ $N$

输出

打印输出答案。

示例输入1

?0?
2

示例输出1

1

如问题描述所示，$T=\lbrace 0,1,4,5\rbrace$。其中，$0$和$1$小于或等于$N$，所以应该打印它们中的最大值$1$。

示例输入2

101
4

示例输出2

-1

我们有$T=\lbrace 5\rbrace$，它不包含小于或等于$N$的值。

示例输入3

?0?
1000000000000000000

示例输出3

5