Tiling the Wall with Square Frames

This problem is adapted from the PA 2024 Runda 3 Obrazy problem. You are given a rectangular wall of size \(h \times w\) and \(n\) types of square frames. An unlimited number of frames is available for each type. It is guaranteed that for any two different frame sizes, the side length of one always divides the side length of the other.

The task is to completely cover the wall using these frames. Frames may touch only at their edges and must not overlap. Find the minimum number of frames required to tile the wall exactly. If it is not possible to cover the wall completely, output \(-1\).

Note: All formulas are written in \(\LaTeX\) format. For example, the wall has size \(h \times w\) and if tiling is impossible, the output is \(-1\).

inputFormat

The input consists of two lines.

• The first line contains three integers \(h\), \(w\), and \(n\) (the height, width of the wall and the number of frame types).
• The second line contains \(n\) positive integers. Each integer represents the side length of a square frame. It is guaranteed that for any two distinct frame sizes \(a\) and \(b\), either \(a\) divides \(b\) or \(b\) divides \(a\).

outputFormat

Output a single integer: the minimum number of frames needed to completely cover the wall. If it is impossible to tile the wall exactly, output \(-1\).

sample

6 5 2
1 2

12