{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003e\r\nFamous ancient Greek sculptor Phidias is making preparations to build another marvellous\r\nmonument. For this purpose he needs rectangular marble plates of sizes W1 x H1, W2 x\r\nH2, ..., WN x HN.\u003cbr\u003e\u003cbr\u003e\r\n\r\nRecently, Phidias has received a large rectangular marble slab. He wants to cut the slab to\r\nobtain plates of the desired sizes. Any piece of marble (the slab or the plates cut from it) \r\ncan be cut either horizontally or vertically into two rectangular plates with integral widths \r\nand heights, cutting completely through that piece. This is the only way to cut pieces and \r\npieces cannot be joined together. Since the marble has a pattern on it, the plates cannot be \r\nrotated: if Phidias cuts a plate of size A ? B then it cannot be used as a plate of size B ? A \r\nunless A \u003d B. He can make zero or more plates of each desired size. A marble plate is wasted if \r\nit is not of any of the desired sizes after all cuts are completed. Phidias wonders how to cut \r\nthe initial slab so that as little of it as possible will be wasted.\u003cbr\u003e\u003cbr\u003e\r\n\r\nAs an example, assume that in the figure below the width of the original slab is 21 and the\r\nheight of the original slab is 11, and the desired plate sizes are 10 x 4, 6 x 2, 7 x 5, and 15 \r\nx 10. The minimum possible area wasted is 10, and the figure shows one sequence of cuts\r\nwith total waste area of size 10.\u003cbr\u003e\u003c/p\u003e\r\n\u003ch3\u003e\u003cimg src\u003d\"CDN_BASE_URL/813855f04fad65786de765cd9856bf95?v\u003d1714850772\"\u003e\u003c/h3\u003e\u003cbr\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\nYour task is to write a program that, given the size of the original slab and the desired plate\r\nsizes, calculates the minimum total area of the original slab that must be wasted.\u003cbr\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003e\r\nt - the number of test cases, then t test cases follow [t \u0026lt;\u003d 20]. \r\n\r\nThe first line of each test case contains two integers: first W, the width of the original slab, and then H, the height of the original slab. The second line contains one integer N: the number of desired plate sizes. The following N lines contain the desired plate sizes. Each of these lines contains two integers: first the width Wi and then the height Hi of that desired plate size (1 \u0026lt;\u003d i \u0026lt;\u003d N). [1 \u0026lt;\u003d W \u0026lt;\u003d 600, 1 \u0026lt;\u003d H \u0026lt;\u003d 600, 0 \u0026lt; N \u0026lt;\u003d 200, 1 \u0026lt;\u003d Wi \u0026lt;\u003d W, and 1 \u0026lt;\u003d Hi \u0026lt;\u003d H.]\u003cbr\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case output one line with a single integer: the minimum total area of the original slab that must be wasted.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n21 11\r\n4\r\n10 4\r\n6 2\r\n7 5\r\n15 10\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\u003c/div\u003e"}}]}