여행 (2007)

어느 동아리 학생들은 매년 이국적인 장소로 여행을 떠난다. 지금까지 다녀온 곳으로는 인디애나폴리스, 피닉스, 내슈빌, 필라델피아, 산호세, 애틀랜타, 아인트호벤, 올랜도, 밴쿠버, 호놀룰루, 베벌리힐스, 프라하, 상하이, 샌안토니오 등이 있다. 올봄에도 비슷한 여행을 계획하고 있지만 어디로 언제 갈지는 아직 정하지 못했다.

문제는 후한 후원자들이 늘 여러 개의 배낭과 가방을 선물로 주기 때문에, 집으로 돌아올 때 이것들을 모두 챙겨야 한다는 점이다. 항공사가 허용하는 수하물 개수가 제한되어 있으므로, 학생들은 선물을 한데 모아 가방을 서로 포개어 넣어(한 가방 안에 다른 가방을 넣어) 들고 가야 하는 짐(가장 바깥쪽 가방)의 총 개수를 최소로 만들기로 했다.

모든 가방은 모양이 완전히 같고 크기(선형 치수)만 다르며, 이 크기는 $1000000$ 이하의 양의 정수이다. 크기가 더 작은 가방은 더 큰 가방 안에 들어가지만, 크기가 같은 두 가방은 서로 포갤 수 없다. 모든 가방을 담는 데 필요한 짐(가장 바깥쪽 가방)의 최소 개수를 구하여라. 또한 그 최소 개수의 짐을 사용하는 모든 방법 중에서, 가장 많은 가방이 들어 있는 짐의 가방 수(그 짐에 포개진 가방을 모두 센 값으로, 가장 바깥 가방도 포함한다)를 최소로 했을 때의 값을 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 가방의 개수를 나타내는 정수 $1 \le n \le 10000$ 으로 시작하고, 이어서 $n$ 개의 정수가 한 줄 또는 여러 줄에 걸쳐 주어지며 각 정수는 가방 하나의 크기이다. 마지막 테스트 케이스 뒤에는 $0$ 하나만 있는 줄이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 두 정수를 공백 하나로 구분하여 한 줄에 출력한다. 짐의 최소 개수 $k$ 와, 정확히 $k$ 개의 짐을 사용하는 모든 방법 중에서 가장 많은 가방이 들어 있는 짐의 가방 수를 최소로 했을 때의 값 $m$ 이다. 테스트 케이스가 주어진 순서대로 한 줄씩 출력한다.