{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e.content-description h4 {\n font-size: 1.4em;\n border-bottom: 1px solid #eee;\n line-height: 1.225;\n padding-bottom: 0.3em;\n padding-top: 0.5em;\n font-weight: 700;\n}.content-description img {\n max-width: 100%;\n height: auto;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content-description screen\"\u003e\n\u003cdiv\u003e\u003ch5\u003eIOI \u002704 - Athens, Greece\u003c/h5\u003e\n\u003cp\u003eFamous ancient Greek sculptor Phidias is making preparations to build\nanother marvelous monument. For this purpose he needs rectangular marble\nplates of sizes \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/f308ecc4effc997ea201d84f6537e39a?v\u003d1719618425\" style\u003d\"vertical-align: -0.671ex; width:34.708ex; height:2.509ex;\" alt\u003d\"W_1 \\times H_1, W_2 \\times H_2, \\dots, W_N \\times H_N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~W_1 \\times H_1, W_2 \\times H_2, \\dots, W_N \\times H_N~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eRecently, Phidias has received a large rectangular marble slab. He wants\nto cut the slab to obtain plates of the desired sizes. Any piece of\nmarble (the slab or the plates cut from it) can be cut either\nhorizontally or vertically into two rectangular plates with integral\nwidths and heights, cutting completely through that piece. This is the\nonly way to cut pieces and pieces cannot be joined together. Since the\nmarble has a pattern on it, the plates cannot be rotated: if Phidias\ncuts a plate of size \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c37a80652e2073f122dab3dc85ce49b0?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:6.347ex; height:2.176ex;\" alt\u003d\"A \\times B\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~A \\times B~\u003c/span\u003e\u003c/span\u003e then it cannot be used as a plate of size\n\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/9566e9f666ea323e270dd6fcc68ec0aa?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:6.347ex; height:2.176ex;\" alt\u003d\"B \\times A\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~B \\times A~\u003c/span\u003e\u003c/span\u003e unless \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/5226616595cb1319a972fa2aeeb5d65c?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:6.606ex; height:2.176ex;\" alt\u003d\"A \u003d B\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~A \u003d B~\u003c/span\u003e\u003c/span\u003e. He can make zero or more plates of each\ndesired size. A marble plate is wasted if it is not of any of the\ndesired sizes after all cuts are completed. Phidias wonders how to cut\nthe initial slab so that as little of it as possible will be wasted.\u003c/p\u003e\n\u003cp\u003eAs an example, assume that in the figure below the width of the original\nslab is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e7e23e2a77ce09fa69c1b5a18aa20861?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"21\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~21~\u003c/span\u003e\u003c/span\u003e and the height of the original slab is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d6c8ed0de560f88fa572eb1ec2aca1c6?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"11\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~11~\u003c/span\u003e\u003c/span\u003e, and the desired\nplate sizes are \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/ef6ed02e8afc7c758add1664879c0749?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:6.328ex; height:2.176ex;\" alt\u003d\"10 \\times 4\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~10 \\times 4~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/9b66b08e372364886fd7c44e6b01f211?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:5.165ex; height:2.176ex;\" alt\u003d\"6 \\times 2\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~6 \\times 2~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0fa44fd4826453fda9f590d035fe7954?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:5.165ex; height:2.176ex;\" alt\u003d\"7 \\times 5\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~7 \\times 5~\u003c/span\u003e\u003c/span\u003e, and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/94ba8a64dfcbaa25f227eb0f15208ab2?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:7.49ex; height:2.176ex;\" alt\u003d\"15 \\times 10\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~15 \\times 10~\u003c/span\u003e\u003c/span\u003e. The minimum possible\narea wasted is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e604467303f21c656febff5848d33242?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"10\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~10~\u003c/span\u003e\u003c/span\u003e, and the figure shows one sequence of cuts with total\nwaste area of size \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e604467303f21c656febff5848d33242?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"10\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~10~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cdiv style\u003d\"max-width: 100%;height: 196;max-height: 196;width: 374;text-align: center;\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/8366c905ff1950079418fb3b816d6e61?v\u003d1719618425\" class\u003d\"tex-full\" width\u003d\"374\" height\u003d\"196\"\u003e\u003c/div\u003e\u003cp\u003eYour task is to write a program that, given the size of the original\nslab and the desired plate sizes, calculates the minimum total area of\nthe original slab that must be wasted.\u003c/p\u003e\n\u003ch4\u003eInput Specification\u003c/h4\u003e\n\u003cp\u003eThe first line of input contains two integers: first \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/f42baa1a3e08d363e273653abfabed49?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:2.435ex; height:2.176ex;\" alt\u003d\"W\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~W~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7f950627b75b6c334dd56e4178230376?v\u003d1719618425\" style\u003d\"vertical-align: -0.838ex; width:15.091ex; height:2.843ex;\" alt\u003d\"(1 \\le W \\le 600)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le W \\le 600)~\u003c/span\u003e\u003c/span\u003e,\nthe width of the original slab, and then \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/367c5dacf7f2ffdd724dec89e86a1e3c?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"H\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~H~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7a7f4808fda92e283aa7004967a2509e?v\u003d1719618425\" style\u003d\"vertical-align: -0.838ex; width:14.72ex; height:2.843ex;\" alt\u003d\"(1 \\le H \\le 600)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le H \\le 600)~\u003c/span\u003e\u003c/span\u003e,\nthe height of the original slab. The second line contains one integer\n\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/65725de7de395afef918f7827d173330?v\u003d1719618425\" style\u003d\"vertical-align: -0.838ex; width:14.72ex; height:2.843ex;\" alt\u003d\"(0 \u003c N \\le 200)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(0 \u0026lt; N \\le 200)~\u003c/span\u003e\u003c/span\u003e: the number of desired plate sizes. The following\n\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e lines contain the desired plate sizes. Each of these lines contains\ntwo integers: first the width \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/df95765c65c9260a263fedcab8df16a4?v\u003d1719618425\" style\u003d\"vertical-align: -0.671ex; width:2.993ex; height:2.509ex;\" alt\u003d\"W_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~W_i~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/270c0917bd6326e41b3f671a3f9c37bd?v\u003d1719618425\" style\u003d\"vertical-align: -0.838ex; width:14.597ex; height:2.843ex;\" alt\u003d\"(1 \\le W_i \\le W)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le W_i \\le W)~\u003c/span\u003e\u003c/span\u003e and then the\nheight \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/52607d3a870bc66c6fcacb111cde3788?v\u003d1719618425\" style\u003d\"vertical-align: -0.671ex; width:2.731ex; height:2.509ex;\" alt\u003d\"H_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~H_i~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/3d76ecb98b43b49ef0544fe5bb563005?v\u003d1719618425\" style\u003d\"vertical-align: -0.838ex; width:13.963ex; height:2.843ex;\" alt\u003d\"(1 \\le H_i \\le H)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le H_i \\le H)~\u003c/span\u003e\u003c/span\u003e of that desired plate size.\u003c/p\u003e\n\u003ch4\u003eOutput Specification\u003c/h4\u003e\n\u003cp\u003eThe output should contain one line with a single integer: the minimum\ntotal area of the original slab that must be wasted.\u003c/p\u003e\n\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e21 11\n4\n10 4\n6 2\n7 5\n15 10\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003eNote: in \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d345add568b987fff4d22bd0b5781a7d?v\u003d1719618425\" style\u003d\"vertical-align: -0.338ex; width:4.261ex; height:2.343ex;\" alt\u003d\"50\\%\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~50\\%~\u003c/span\u003e\u003c/span\u003e of the inputs, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a5017cba2d13a874fe4cd1708e0bd14c?v\u003d1719618425\" style\u003d\"vertical-align: -0.505ex; width:7.859ex; height:2.343ex;\" alt\u003d\"W \\le 20\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~W \\le 20~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/5b1687c3b4e00f6b2c14f991dfec627d?v\u003d1719618425\" style\u003d\"vertical-align: -0.505ex; width:7.487ex; height:2.343ex;\" alt\u003d\"H \\le 20\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~H \\le 20~\u003c/span\u003e\u003c/span\u003e, and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/b05b0f235820d7b60601930e805691d4?v\u003d1719618425\" style\u003d\"vertical-align: -0.505ex; width:6.325ex; height:2.343ex;\" alt\u003d\"N \\le 5\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N \\le 5~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003c/div\u003e\n\u003chr\u003e\n\n\u003c/div\u003e"}}]}