29523번 - Большое множество 다국어

문제

Чего только не творится в Недалеком королевстве. Волшебник Мерлин и рыцарь Артур иногда развлекаются тем, что Мерлин доказывает Артуру, что некоторое множество $S$ большое. При этом множество такое большое, что Мерлин не может предъявить Артуру все элементы этого множества. Недавно они изобрели отличный способ доказательства: Артур выбирает случайным образом хеш-функцию $h$ и число $y,ドル а Мерлин предъявляет Артуру $s \in S,ドル такое что $h(s) = y$. Они даже прочитали в каком-то древнем манускрипте, что можно строго доказать, что этот метод работает, если должным образом определить понятия <<большого множества>> и <<случайной хеш-функции>>. Но теперь они пошли дальше и придумали двухэтапную схему.

Рассмотрим функцию $f$. Будем говорить, что $y$ является $k$-хорошим, если множество $S_y = \{s \in S\text{ и }f(s)=y\}$ содержит хотя бы $k$ элементов. Если Мерлин докажет, что множество $G$ значений, которые являются $k$-хорошими, содержит хотя бы $d$ элементов, это означает, что $S$ имеет размер хотя бы $kd$.

Рассмотрим множество $S,ドル содержащее $n$ элементов и функцию $f,ドル принимающую целые значения от 1 до $m$. Артура заинтересовал худший случай: каково максимальное $z,ドル такое что, какова бы не была функция $f,ドル Мерлин сможет, воспользовавшись описанной схемой, доказать, что в множестве $S$ хотя бы $z$ элементов. При этом Мерлин может выбрать $k$ и $d,ドル но он может доказать Артуру только истинные утверждения про размеры множеств.

Например, пусть $n = 5,ドル а $m = 2$. Тогда Мерлин может доказать, что в $S$ хотя бы 4 элемента. Действительно, если $f$ отображает все элементы $S$ в одно и то же число, то Мерлин доказывает, что хотя бы 1 значение является 5-хорошим. Если $f$ отображает 1 элемент в одно значение и 4 остальных в другое, то Мерлин доказывает, что хотя бы 1 значение 4-хорошее. Наконец, если $f$ отображает 2 элемента в одно значение и 3 элемента в другое, то Мерлин доказывает, что 2 элемента являются 2-хорошими. В любом случае Артур убеждается, что в $S$ содержится хотя бы 4 элемента.

입력

Входной файл содержит два числа: $n$ и $m$ (1ドル \le n \le 10^{18},ドル 1ドル \le m \le 100,000円$).

출력

Выведите одно число $z$ --- максимальное число, такое что для любой функции $f:S \to \{1,\ldots,m\}$ Мерлин может доказать, что хотя бы $d$ значений являются $k$-хорошими для таких $d$ и $k,ドル что $dk \ge z$.

제한

힌트