창고 선반의 빈 칸

문제

한 물류 창고에 같은 크기의 상자들이 도착했다. 창고 담당자는 이 상자들을 모두 같은 모양의 선반에 보관하려 한다. 선반 하나는 여러 층으로 이루어져 있고, 각 층에는 상자를 놓는 칸이 일렬로 나뉘어 있다. 모든 칸의 크기는 같으며 한 칸에는 상자를 정확히 하나만 놓을 수 있다. 선반 하나의 층수는 H이고, 각 층의 칸 수는 W다. 따라서 선반 하나에는 H와 W를 곱한 수만큼의 상자를 보관할 수 있다. 상자는 모두 한 칸에 들어가는 크기이며, 방향을 바꾸거나 다른 상자와 포개어 한 칸에 여러 개를 놓을 수는 없다. 선반 사이에 상자를 걸쳐 놓거나 바닥에 따로 보관하는 것도 허용하지 않는다. 이번에 보관해야 할 상자는 N개다. 창고에는 비어 있는 선반이 충분히 많으며, 담당자는 필요한 선반만 골라 사용한다. 사용한 선반의 수가 가장 적어지도록 모든 상자를 배치한 뒤, 사용한 선반 안에서 상자가 놓이지 않은 칸의 수를 기록하려 한다. 사용하지 않은 선반의 칸은 빈 칸 수에 포함하지 않는다. 예를 들어 선반을 여러 개 사용한다면 앞선 선반을 모두 채우고 마지막 선반에 남은 상자를 놓아도 된다. 다만 문제에서 구하는 것은 상자를 놓은 구체적인 순서나 위치가 아니라, 최소로 필요한 선반 수와 그 선반들에 남는 빈 칸 수다. 상자 배치가 여러 가지여도 이 두 수는 같다. 상자가 하나도 도착하지 않은 경우에는 선반을 사용하지 않는다. 이때 필요한 선반 수와 빈 칸 수는 모두 0이다. 상자가 선반들을 빈틈없이 채우는 경우에도 빈 칸 수는 0이다. 주어진 상자 수, 층수, 층마다의 칸 수를 이용하여 담당자가 기록할 두 정수를 구한다.

입력

한 줄에 상자 수 N, 선반 하나의 층수 H, 각 층의 칸 수 W가 공백으로 구분되어 주어진다. 모든 입력은 정수이며, 0 ≤ N ≤ 1,000, 1 ≤ H ≤ 1,000, 1 ≤ W ≤ 1,000이다.

출력

최소로 필요한 선반 수와 사용한 선반에 남는 빈 칸 수를 순서대로 공백 하나로 구분하여 한 줄에 출력한다. N이 0이면 0 0을 출력한다.

29 3 4

3 7

0 5 8

0 0

48 4 6

2 0

출처: Devin.KR 자체 제작