큰 집합

어리석은 왕국에서는 별일이 다 일어난다. 마법사 멀린과 기사 아서는 가끔 멀린이 어떤 집합 $S$가 크다는 것을 아서에게 증명하는 놀이를 한다. 집합이 너무 커서 멀린은 원소를 전부 아서에게 보여줄 수 없다. 최근 두 사람은 좋은 증명 방법을 찾아냈다. 아서가 무작위로 해시 함수 $h$와 수 $y$를 고르면, 멀린은 $h(s) = y$를 만족하는 $s \in S$를 보여준다. 옛 필사본에는 '큰 집합'과 '무작위 해시 함수'를 제대로 정의하면 이 방법이 맞는다는 것을 엄밀하게 증명할 수 있다고 적혀 있었다. 하지만 이제 두 사람은 한 걸음 더 나아가 2단계 방식을 고안했다.

함수 $f$를 생각하자. $S_y = \{s \in S \mid f(s)=y\}$의 원소가 $k$개 이상이면 $y$를 $k$-좋은 값이라고 한다. 멀린이 $k$-좋은 값들의 집합 $G$가 $d$개 이상의 원소를 가진다는 것을 증명하면, $S$의 크기는 적어도 $kd$이다.

원소가 $n$개인 집합 $S$와, 1부터 $m$까지의 정수 값을 갖는 함수 $f$를 생각하자. 아서는 최악의 경우에 관심이 있다. 어떤 함수 $f$가 주어지더라도, 멀린이 위의 방법으로 $S$의 원소가 적어도 $z$개 있다고 증명할 수 있는 최대 $z$는 얼마인가? 멀린은 $k$와 $d$를 고를 수 있지만, 집합의 크기에 관한 참인 주장만 증명할 수 있다.

입력 파일에는 두 수 $n$과 $m$이 들어 있다 ($1 \le n \le 10^{18}$, $1 \le m \le 100000$).

한 개의 수 $z$를 출력하라. $z$는 최대 수이며, 임의의 함수 $f:S \to \{1,\ldots,m\}$에 대해, $dk \ge z$를 만족하는 어떤 $d$와 $k$에 대하여 멀린이 $k$-좋은 값이 적어도 $d$개 있다고 증명할 수 있어야 한다.