시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB4349112881326.560%

문제

세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...)

세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필요한 큐브의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

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

둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다.

셋째 줄부터 총 N개의 줄에 큐브의 종류 Ai와 개수 Bi가 i가 증가하는 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2i에서 i이다.

출력

첫째 줄에 필요한 큐브의 개수의 최솟값을 출력한다. 만약 채울 수 없다면 -1을 출력한다.

제한

  • 1 ≤ length, width, height ≤ 106
  • 1 ≤ n ≤ 20
  • 0 ≤ Ai < 20
  • 0 ≤ Bi ≤ 106
  • Ai ≠ Aj (i ≠ j)

예제 입력 1

4 4 8
3
0 10
1 10
2 1

예제 출력 1

9

예제 입력 2

4 4 8
3
0 10
1 10
2 10

예제 출력 2

2

예제 입력 3

10 10 11
1
0 2000

예제 출력 3

1100

예제 입력 4

10 10 11
1
0 1099

예제 출력 4

-1

예제 입력 5

37 42 59
6
0 143821
1 14382
2 1438
3 143
4 14
5 1

예제 출력 5

5061

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: ho94949