Box Filling

You are given a rectangular box with dimensions length, width, and height. Fill the box completely with cube-shaped blocks.

Each cube has side length 1, 2, 4, 8, ..., a power of two. Given the available cube sizes and counts, find the minimum number of cubes needed to fill the entire box.

The first line contains three natural numbers, length width height.

The second line contains N, the number of available cube types.

Each of the next N lines contains a cube type Ai and a count Bi, given in increasing order of Ai. Type Ai means that the cube side length is 2^Ai.

Print the minimum number of cubes needed to fill the box. If the box cannot be filled exactly, print -1.

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