{"problem":{"name":"[PA 2024] Obrazy","description":{"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 提供翻译** 给定尺寸为 $h\\times w$ 的矩形墙面，以及 $n$ 种尺寸的正方形画框，每种尺寸画框都","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10358"},"statements":[{"statement_type":"Markdown","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$。\n\n## Input\n\n第一行两个整数 $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$ 整除。\n\n## Output\n\n输出一行一个整数，如果可以完全覆盖墙面，输出最少要购买多少画框，否则输出 $-1$。\n\n[samples]\n\n## Background\n\nPA 2024 3C\n\n## Note\n\n在第一个样例中，Byteasar 可以用九个画框（六个 $1\\times 1$、两个 $3\\times 3$ 和一个 $6\\times 6$）覆盖一面墙，具体如下：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/t6g3zuws.png)\n\n在第二个样例中，无法完全覆盖墙面。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10358","tags":["数学","贪心","2024","PA（波兰）"],"sample_group":[["6 10\n3\n1 3 6\n","9\n"],["3 3\n1\n2\n","-1"]],"created_at":"2026-03-03 11:09:25"}}