鸡蛋的硬度

题目描述

已知楼高为 $n$（共 $n$ 层），你有 $m$ 个鸡蛋，它们的硬度相同。

鸡蛋的硬度是一个整数 $x$（$0\le x\le n$）：硬度为 $x$ 的鸡蛋，从高度不超过 $x$ 的楼层扔下一定不会碎，从高于 $x$ 的楼层扔下一定会碎；未碎的鸡蛋可以继续使用。可以认为在 $n+1$ 层扔下时鸡蛋一定会碎。

你需要通过若干次“从某一层扔下鸡蛋并观察是否碎裂”的实验来确定鸡蛋的硬度。求在最坏情况下所需的最少实验次数。

输入格式

输入包含多组数据，每组数据一行，包含两个正整数 $n,m$（$1\le n\le 100$，$1\le m\le 10$），分别表示楼高和鸡蛋个数。

输出格式

对于每组数据，输出一行一个整数，表示最优策略在最坏情况下所需的扔鸡蛋次数。

样例输入

100 1
100 2

样例输出

100
14

提示

最优策略指使“最坏情况下的扔鸡蛋次数”最少的策略。

若只有 $1$ 个鸡蛋，只能从第 $1$ 层开始逐层尝试；最坏情况下鸡蛋硬度为 $100$，需要扔 $100$ 次。若采用其它策略，可能无法确定硬度（例如第一次在第二层扔，若碎了便无法区分硬度是 $0$ 还是 $1$），此时最坏情况下需要扔无限次，因此第一组数据的答案是 $100$。

限制

每组数据 $1\text{s}$，$1024\text{KiB}$。