P10358 [PA 2024] Obrazy

PA 2024 3C

**This problem is translated from Round 3 [Obrazy](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/obr/) of [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/). 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$.

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

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

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