题目描述

给你两个整数 $m(0 \le m \le 10^{18})$ 和 $k(1 \le k \le 64)$，请找出满足如下条件的最小正整数 $n$：

在 $n+1,n+2, \ldots, a \cdot n$ 中恰好有 $m$ 个整数的二进制表示中有 $k$ 位为 $1$。

数据保证 $n$ 必然存在且不超过 $10^{18}$。

输入格式

输入共一行，包含两个整数 $m$ 和 $k$，以一个空格分隔（$0 \le m \le 10^{18}, 1 \le k \le 64$）。

输出格式

输出满足条件的最小正整数 $n(1 \le n \le 10^{18})$。

样例

1 1

1

3 2

5

样例 1 解释

样例1中，$n=1$，

• $n+1=2=(10)_2$，二进制表示包含 $1$ 位 $1$，满足条件。

共 $1$ 个数满足条件。

样例 2 解释

样例2中，$n=5$，

• $6 = (110)_2$，二进制表示中包含 $2$ 位 $1$，满足条件；
• $7 = (111)_2$，二进制表示中包含 $3$ 位 $1$，不满足条件；
• $8 = (1000)_2$，二进制表示中包含 $1$ 位 $1$，不满足条件；
• $9 = (1001)_2$，二进制表示中包含 $2$ 位 $1$，满足条件；
• $10 = (1010)_2$，二进制表示中包含 $2$ 位 $1$，满足条件。

共 $3$ 个数满足条件。

同样能够证明，当 $n=1$ 时，共 $0$ 个数满足条件；当 $n=2$ 时，共 $1$ 个数满足条件；当 $n=3$ 时，共 $2$ 个数满足条件；当 $n=4$ 时，共 $2$ 个数满足条件，所以 $5$ 是最小的满足条件的答案。

数据范围

• 对于 $20\%$ 的数据，$m \le 1000, k \le 10$；
• 对于 $40\%$ 的数据，$m \le 10^9, k \le 30$；
• 对于 $100\%$ 的数据，$0 \le m \le 10^{18}, 1 \le k \le 64$。