박스 채우기

길이가 length, 너비가 width, 높이가 height인 직육면체 상자가 있다. 이 상자를 정육면체 모양의 큐브들로 빈틈없이 채우려고 한다.

각 큐브의 한 변의 길이는 1, 2, 4, 8, ...처럼 2의 거듭제곱이다. 사용할 수 있는 큐브의 크기와 개수가 주어질 때, 상자를 모두 채우는 데 필요한 큐브 수의 최솟값을 구하라.

첫째 줄에 세 자연수 length width height가 주어진다.

둘째 줄에 사용할 수 있는 큐브 종류의 수 N이 주어진다.

다음 N개의 줄에는 큐브의 종류 Ai와 개수 Bi가 Ai가 증가하는 순서대로 주어진다. 종류 Ai는 그 큐브의 한 변의 길이가 2^Ai임을 뜻한다.

상자를 채우는 데 필요한 큐브 개수의 최솟값을 출력한다. 상자를 빈틈없이 채울 수 없다면 -1을 출력한다.

• 1 <= length, width, height <= 10^6
• 1 <= N <= 20
• 0 <= Ai < 20
• 0 <= Bi <= 10^6
• Ai != Aj (i != j)