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$.