Background

PA 2024 3C

Problem Description

This problem is translated from Round 3 Obrazy of PA 2024. Thanks to Macaronlin for the translation.

You are given a rectangular wall of size $h\times w$, and $n$ types of square picture frames with different sizes. For each size, there are infinitely many frames available. For any two different frame sizes, the side length of one size always divides the side length of the other.

Now use these frames to completely cover the wall, with no overlaps allowed; frames may only touch along edges. Find the minimum number of frames that need to be bought. If it is impossible to cover the wall completely, output $-1$.

Input Format

The first line contains two integers $h$ and $w$ $(1\le h,w\le 10^9)$, denoting the wall size.

The second line contains an integer $n$ $(1\le n\le 30)$, denoting the number of frame sizes.

The third line contains $n$ integers $d_1,d_2,\ldots,d_n$ $(1\le d_i\le 10^9,d_i<d_{i+1})$, denoting the side length of each square frame. It is guaranteed that $d_{i+1}$ is divisible by $d_i$.

Output Format

Output one integer on one line. If the wall can be fully covered, output the minimum number of frames to buy; otherwise output $-1$.

6 10
3
1 3 6

9

3 3
1
2

-1

Hint

In the first sample, Byteasar can cover a wall using nine frames (six $1\times 1$, two $3\times 3$, and one $6\times 6$), as shown below.

In the second sample, it is impossible to fully cover the wall.

Translated by ChatGPT 5