{"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\nNghệ sĩ điêu khắc nổi tiếng của Hy Lạp cổ đại Phidias đang chuẩn bị xây dựng một công trình kỳ diệu khác. Vì mục đích này, anh cần các tấm đá hoa cương hình chữ nhật có kích thước W1 x H1, W2 x H2, ..., WN x HN.\u003cbr\u003e\u003cbr\u003e\r\n\r\nGần đây, Phidias đã nhận được một tấm đá hoa cương hình chữ nhật lớn. Anh muốn cắt tấm đá này để có được các tấm đá theo kích thước mong muốn. Bất kỳ mảnh đá nào (tấm đá hoặc các tấm cắt từ nó) đều có thể được cắt theo chiều ngang hoặc dọc thành hai tấm đá hình chữ nhật có chiều rộng và chiều cao nguyên, cắt hoàn toàn qua mảnh đó. Đây là cách duy nhất để cắt mảnh và các mảnh không thể được ghép lại với nhau. Vì đá hoa cương có một mẫu trên đó, các tấm đá không thể được xoay: nếu Phidias cắt một tấm có kích thước A ? B thì nó không thể được sử dụng như một tấm có kích thước B ? A trừ khi A \u003d B. Anh có thể tạo ra không hoặc nhiều tấm theo mỗi kích thước mong muốn. Một tấm đá hoa cương bị lãng phí nếu nó không phải là bất kỳ kích thước mong muốn nào sau khi tất cả các cắt được hoàn thành. Phidias tự hỏi làm thế nào để cắt tấm đá ban đầu sao cho ít nhất có thể bị lãng phí.\u003cbr\u003e\u003cbr\u003e\r\n\r\nVí dụ, giả sử trong hình dưới đây, chiều rộng của tấm đá ban đầu là 21 và chiều cao của tấm đá ban đầu là 11, và các kích thước tấm mong muốn là 10 x 4, 6 x 2, 7 x 5, và 15 x 10. Diện tích lãng phí tối thiểu có thể là 10, và hình dưới đây cho thấy một chuỗi cắt với diện tích lãng phí tổng cộng là 10.\u003cbr\u003e\u003c/p\u003e\r\n\u003ch3\u003e\u003cimg src\u003d\"CDN_BASE_URL/813855f04fad65786de765cd9856bf95?v\u003d1704136701\"\u003e\u003c/h3\u003e\u003cbr\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\nNhiệm vụ của bạn là viết một chương trình, với kích thước của tấm đá ban đầu và các kích thước tấm mong muốn, tính toán diện tích tổng cộng tối thiểu của tấm đá ban đầu mà phải bị lãng phí.\u003cbr\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003ch3\u003eNhập vào\u003c/h3\u003e\r\n\u003cp\u003e\r\nt - số lượng các bộ test, sau đó là t bộ test [t \u0026lt;\u003d 20]. \r\n\r\nDòng đầu tiên của mỗi bộ test chứa hai số nguyên: trước tiên là W, chiều rộng của tấm đá ban đầu, và sau đó là H, chiều cao của tấm đá ban đầu. Dòng thứ hai chứa một số nguyên N: số lượng kích thước tấm mong muốn. N dòng tiếp theo chứa các kích thước tấm mong muốn. Mỗi dòng trong số này chứa hai số nguyên: trước hết là chiều rộng Wi và sau đó là chiều cao Hi của kích thước tấm mong muốn đó (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, và 1 \u0026lt;\u003d Hi \u0026lt;\u003d H.]\u003cbr\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eĐầu ra\u003c/h3\u003e\r\n\u003cp\u003eĐối với mỗi bộ test, xuất ra một dòng với một số nguyên duy nhất: diện tích tổng cộng tối thiểu của tấm đá ban đầu mà phải bị lãng phí.\u003c/p\u003e\r\n\r\n\u003ch3\u003eVí dụ\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"}}]}