시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 103 21 15 24.194%

문제

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

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

입력

첫째 줄에 length width height가 주어진다. 이 모든 값은 10^6보다 작거나 같은 자연수이다. 둘째 줄에 세준이가 가지고 있는 큐브의 종류의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 셋째 줄부터 총 N개의 줄에 큐브의 종류 개수 순서대로 주어진다. 큐브의 종류는 한 변의 길이를 나타낼 때 쓰는 2^i에서 i이다. 개수는 10^6보다 작거나 같은 음이아닌 정수이다.

출력

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

예제 입력

4 4 8
3
0 10
1 10
2 1

예제 출력

9

힌트

출처