{"raw_statement":[{"iden":"background","content":"PA 2024 3C"},{"iden":"statement","content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 3 [Obrazy](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/obr/)，感谢 Macaronlin 提供翻译**\n\n给定尺寸为 $h\\times w$ 的矩形墙面，以及 $n$ 种尺寸的正方形画框，每种尺寸画框都有无穷多个。对于任意两种不同尺寸的画框，其中一个尺寸的边长总能整除另一个尺寸的边长。\n\n现用这些画框完全覆盖墙面，而且画框之间不能重叠，只能边缘相接，请求出最少需要购买多少个画框？如果不可能完全覆盖墙面，则程序应输出 $-1$。"},{"iden":"input","content":"第一行两个整数 $h$ 和 $w\\ (1\\le h,w\\le 10^9)$，表示墙面大小。\n\n第二行一个整数 $n\\ (1\\le n\\le 30)$，表示画框个数。\n\n第三行 $n$ 个整数 $d_1,d_2,\\ldots,d_n\\ (1\\le d_i\\le 10^9,d_i<d_{i+1})$，表示每个正方形画框的大小，保证 $d_{i+1}$ 能被 $d_i$ 整除。"},{"iden":"output","content":"输出一行一个整数，如果可以完全覆盖墙面，输出最少要购买多少画框，否则输出 $-1$。"},{"iden":"note","content":"在第一个样例中，Byteasar 可以用九个画框（六个 $1\\times 1$、两个 $3\\times 3$ 和一个 $6\\times 6$）覆盖一面墙，具体如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/t6g3zuws.png)\n\n在第二个样例中，无法完全覆盖墙面。"}],"translated_statement":null,"sample_group":[["6 10\n3\n1 3 6\n","9\n"],["3 3\n1\n2\n","-1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}