무거운 책

캠퍼스의 컴퓨터과학 도서관이 리모델링을 위해 임시로 문을 닫아야 해서, 당신이 도서관의 모든 책을 보관하는 일을 맡게 되었다. 당신이 선택되었다는 사실에 놀라고, 캠퍼스에 컴퓨터과학 도서관이 있었다는 사실에 또 놀란 뒤, 일을 시작한다. 책들은 이미 무게가 모두 같은 똑같은 상자에 포장되어 있다. 보관실에 물이 찰 경우를 대비해 이 상자들을 나무 팔레트 위에 쌓으려고 하는데, 작은 문제가 하나 있다. 팔레트가 무게를 견디지 못하고 무너지기 전까지 상자를 몇 개까지 쌓을 수 있는지 모른다는 것이다. 팔레트 위에 놓을 수 있는 상자의 최대 개수를 상자 한계라고 부르자.

한 팔레트에 상자를 하나 놓고, 그다음에 둘, 셋, 이런 식으로 팔레트가 부서질 때까지 차례대로 놓을 수도 있지만, 시간이 매우 오래 걸릴 것 같다(그리고 매우 지루한 대회 문제가 될 것이다). 하지만 실험해 볼 팔레트가 하나 이상 있다면 상자 한계를 더 빨리 알아낼 수 있을지도 모른다. 예를 들어, 상자의 크기와 보관실 천장 높이 때문에 어떤 더미에도 상자를 최대 $3$개까지만 쌓을 수 있다고 하자. 팔레트가 하나뿐이라면 먼저 상자 하나를 시도할 수 있다. 팔레트가 무너지면 더 튼튼한 팔레트를 구하러 가야 한다. 팔레트가 버티면 상자 두 개를 시도할 수 있다. 이때 팔레트가 무너지면 상자 한계가 $1$임을 알게 된다. 그렇지 않으면 상자 세 개를 시도해서, 팔레트가 무너지면 상자 한계가 $2$, 무너지지 않으면 $3$임을 알게 된다. 이 방법에는 실험이 최대 세 번 필요하다. 그러나 팔레트가 두 개 있다면 실험을 최대 두 번만 해도 상자 한계를 알아낼 수 있다. 먼저 첫 번째 팔레트에 상자 두 개를 시도한다. 팔레트가 버티면 상자 세 개를 시도해서 상자 한계가 $2$인지 $3$인지 알 수 있다. 첫 번째 실험에서 첫 번째 팔레트가 무너지면 두 번째 팔레트를 끌어내어 상자 하나를 놓는다. 그 실험의 결과로 상자 한계가 $1$인지 $0$인지 알 수 있다.

당신은 보관실의 높이(쌓을 수 있는 상자의 최대 개수를 결정한다)와 실험에 사용할 수 있는 팔레트의 개수를 정확히 모른다. 이 정보가 주어졌을 때, 최적의 전략을 사용하면 최악의 경우 실험을 최소 몇 번 해야 하는지 알고 싶다. 컴퓨터과학 도서관에 대해 더 일찍 알았더라면 좋았을 텐데, 어쩌면 책 중 하나에 지금 도움이 될 만한 내용이 있었을지도 모른다.

입력은 두 양의 정수 $n$과 $m$($n \leq 5\,000, m \leq 20$)을 포함하는 한 줄로 이루어진다. $n$은 쌓을 수 있는 상자의 최대 개수(팔레트가 무너지든 무너지지 않든 상관없이)를 나타내고, $m$은 실험에 사용할 수 있는 팔레트의 개수이다.

최적의 전략이 요구하는 최악의 경우 실험 횟수의 최솟값을 출력하고, 그다음에 첫 번째 실험에 사용할 상자의 개수를 출력한다. 첫 번째 실험에 사용할 수 있는 상자의 개수가 범위로 주어지면 이 범위의 최솟값과 최댓값을 하이픈으로 구분하여 출력하고, 그러한 수가 하나뿐이면 그 수만 출력한다.