{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Phú Ông vừa tậu một được ngôi nhà mới rất khang trang ở trung tâm thành phố Kc97ble. Để giúp ngôi nhà thêm đẹp, Phú Ông đã mua một số tấm thảm trải lên sàn để trang trí ngôi nhà của mình.\n\n\u003cp align\u003d\"center\"\u003e\n \u003cimg src\u003d\"https://espresso.codeforces.com/5b0c596f5fe111c5a8b0bc3173e1158c858e713e.png\" /\u003e\n\u003c/p\u003e\n\nMặt sàn ngôi nhà có thể được xem một lưới chữ nhật gồm $M$ dòng và $M$ cột. Các dòng được đánh số từ $1$ đến $M$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $M$ từ trái sang phải. Ô nằm trên dòng $i$ và cột $j$ được gọi là ô $(i, j)$. Phú ông đã mua và trải $K$ tấm thảm, tấm thảm thứ $i$ được miêu tả bởi bốn số nguyên $x_1$, $x_2$, $y_1$, $y_2$ cho biết tấm thảm bao phủ toàn bộ các ô của lưới chữ nhật con có góc trái trên là ô $(x_1, y_1)$ và góc phải dưới là ô $(x_2, y_2)$.\n\nSau khi trải hết tấm thảm, Phú Ông nhận thấy rằng các vị trí các tấm thảm rất bừa bộn. Để làm giảm sự bừa bộn, Phú Ông đã nhờ Bờm tìm cách bỏ đi đúng hai tấm thảm, sao cho số ô không được phủ bởi bất cứ tấm thảm nào còn lại là lớn nhất có thể. Bạn hãy thay mặt Bờm giúp Phú Ông thực hiện điều này nhé.\n"}},{"title":"Dữ liệu","value":{"format":"MD","content":"Dòng đầu tiên gồm số nguyên $T$ cho biết số bộ dữ liệu vào. Mỗi bộ dữ liệu vào được mô tả như sau:\n- Dòng đầu tiên gồm hai số nguyên $N$, $M$ ($3 \\leq N \\leq 300000$, $1 \\leq M \\leq 1500$) - số tấm thảm và kích thước của lưới chữ nhật.\n- $K$ dòng tiếp theo, dòng thứ $i$ gồm bốn số nguyên $x_1$, $x_2$, $y_1$, $y_2$ ($1 \\leq x_1 \\leq x_2 \\leq M$, $1 \\leq y_1 \\leq y_2 \\leq M$) - mô tả tấm thảm thứ $i$.\n\nDữ liệu vào đảm bảo tổng $N$ của các bộ dữ liệu vào không vượt quá $2 \\times 10^6$, và tổng $M^2$ của các bộ dữ liệu vào không vượt quá $5 \\times 10^7$."}},{"title":"Kết quả","value":{"format":"MD","content":"In ra số ô không bị phủ lớn nhất có thể sau khi bỏ đi hai tấm thảm."}},{"title":"Ví dụ","value":{"format":"MD","content":"\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\u003e1\n4 5\n1 1 3 3\n2 2 4 4\n3 3 5 5\n2 3 1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}