{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nYour boss once had got many copies of a treasure map. Unfortunately, all the copies are now broken to many rectangular pieces, and what make it worse, he has lost some of the pieces. Luckily, it is possible to figure out the position of each piece in the original map. Now the boss asks you, the talent programmer, to make a complete treasure map with these pieces. You need to make only one complete map and it is not necessary to use all the pieces. But remember, pieces are not allowed to overlap with each other (See sample 2). \n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003e\nThe first line of the input contains an integer \u003ci\u003eT\u003c/i\u003e (\u003ci\u003eT\u003c/i\u003e \u0026lt;\u003d 500), indicating the number of cases.\n\u003c/p\u003e\n\n\u003cp\u003e\nFor each case, the first line contains three integers \u003ci\u003en\u003c/i\u003e \u003ci\u003em\u003c/i\u003e \u003ci\u003ep\u003c/i\u003e (1 \u0026lt;\u003d \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e \u0026lt;\u003d 30, 1 \u0026lt;\u003d \u003ci\u003ep\u003c/i\u003e \u0026lt;\u003d 500), the width and the height of the map, and the number of pieces. Then \u003ci\u003ep\u003c/i\u003e lines follow, each consists of four integers \u003ci\u003ex1\u003c/i\u003e \u003ci\u003ey1\u003c/i\u003e \u003ci\u003ex2\u003c/i\u003e \u003ci\u003ey2\u003c/i\u003e (0 \u0026lt;\u003d \u003ci\u003ex1\u003c/i\u003e \u0026lt; \u003ci\u003ex2\u003c/i\u003e \u0026lt;\u003d \u003ci\u003en\u003c/i\u003e, 0 \u0026lt;\u003d \u003ci\u003ey1\u003c/i\u003e \u0026lt; \u003ci\u003ey2\u003c/i\u003e \u0026lt;\u003d \u003ci\u003em\u003c/i\u003e), where (x1, y1) is the coordinate of the lower-left corner of the rectangular piece, and (x2, y2) is the coordinate of the upper-right corner in the original map.\n\u003c/p\u003e\n\n\u003cp\u003e\nCases are separated by one blank line.\n\n\u003c/p\u003e\u003ccenter\u003e\n\u003cimg src\u003d\"CDN_BASE_URL/1ee386fdb85ea433f3f7a6fe05cf2f67?v\u003d1715907870\"\u003e\n\u003c/center\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\nIf you can make a complete map with these pieces, output the least number of pieces you need to achieve this.\n\nIf it is impossible to make one complete map, just output -1.\n\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\n\u003cpre\u003e3\n5 5 1\n0 0 5 5\n\n5 5 2\n0 0 3 5\n2 0 5 5\n\n30 30 5\n0 0 30 10\n0 10 30 20\n0 20 30 30\n0 0 15 30\n15 0 30 30\n\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\n\u003cpre\u003e1\n-1\n2\n\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003eHint\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003e\nFor sample 1, the only piece is a complete map.\n\u003c/p\u003e\n\n\u003cp\u003e\nFor sample 2, the two pieces may overlap with each other, so you can not make a complete treasure map.\n\u003c/p\u003e\n\n\u003cp\u003e\nFor sample 3, you can make a map by either use the first 3 pieces or the last 2 pieces, and the latter approach one needs less pieces.\n\u003c/p\u003e\n"}}]}