박스 채우기

시간 제한2초메모리 제한128 MB

요약
가로 세로 높이가 주어진 직육면체를 종류별 개수가 제한된 2의 거듭제곱 크기의 정육면체들로 정확히 채우는 최소 블록 수를 구하고, 불가능하면 -1을 출력합니다.
난이도

보통10점 중 7점

유형
수학, 비트 연산, 그리디, 시뮬레이션
정답자
아직 제출이 없습니다

문제

길이가 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)

예제5

  1. 예제 1

    입력
    4 4 8
3
0 10
1 10
2 1
    예상 출력
    9

  2. 예제 2

    입력
    4 4 8
3
0 10
1 10
2 10
    예상 출력
    2

  3. 예제 3

    입력
    10 10 11
1
0 2000
    예상 출력
    1100

  4. 예제 4

    입력
    10 10 11
1
0 1099
    예상 출력
    -1

  5. 예제 5

    입력
    37 42 59
6
0 143821
1 14382
2 1438
3 143
4 14
5 1
    예상 출력
    5061