题目描述

某天夜里，阿兔正在大楼之间的广场上散步，突然被一个从天而降的鸟蛋结结实实地砸中了脑袋。蛋壳炸裂，蛋液四溅，引发了一场小型社交危机。愤怒的阿兔发誓要找出是哪一层楼的人干的好事。

根据现场分析，阿兔推测鸟蛋是从附近一幢住满鸟人的高楼的某一层以上的楼层扔下来的。该大楼一共有 $n$ 层，编号为 $1$ 到 $n$。阿兔还从物理学家喵博士那里得知了一条关键线索：

• 对于这栋楼存在一个临界楼层 $f$，满足 $0 \leq f \leq n$，从 $f$ 层以上的楼层扔下鸟蛋会碎，从 $f$ 层及以下的楼层扔下鸟蛋不会碎。

为了调查真相，阿兔准备自己进行鸟蛋投掷实验。他可以从任意一层往下扔鸟蛋，并观察是否碎裂。但问题是，他手中鸟蛋数量有限：一共只有 $k$ 个。鸟蛋一旦碎了就无法复用，因此他必须谨慎选择每一次扔鸟蛋的楼层，以便在鸟蛋碎完之前确定临界楼层 $f$。

他希望你告诉他：在最坏情况下，至少要进行多少次鸟蛋投掷试验，才能确保查出临界楼层，对居住在该层以上的鸟人们发起集体诉讼。

输入格式

一行两个正整数 $n$ 和 $k$。

输出格式

输出一个整数，表示在最坏情况下，最少需要多少次鸟蛋投掷试验，才能确保找出临界楼层。

2 1

2

解释 #1

鸟蛋从 $1$ 楼掉落。如果它碎了，肯定能得出 $f = 0$。

否则，鸟蛋从 $2$ 楼掉落。如果它碎了，肯定能得出 $f = 1$。

如果它没碎，那么肯定能得出 $f = 2$。

因此，在最坏的情况下我们需要 $2$ 次鸟蛋投掷试验以确定 $f$ 是多少。

6 2

3

数据范围

• $1 \le n \le 10^{18}$
• $k \in {1, 2}$