{"trustable":true,"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":"HTML","content":"\u003cp\u003eViệc trở thành Ông già Noel rất khó khăn. Đôi khi bạn phải đối mặt với những tình huống khó khăn.\u003c/p\u003e\u003cp\u003eHôm nay Ông già Noel đến ngày lễ và có $$$m$$$ đứa trẻ xếp hàng trước mặt ông. Hãy đánh số cho chúng từ $$$1$$$ đến $$$m$$$. Ông già mặt trời biết $$$n$$$ phép màu. Phép màu thứ $$$i$$$ sẽ cho mỗi đứa trẻ ở vị trí trong phạm vi $$$[L_i, R_i]$$$ nhận một viên kẹo. Mỗi phép màu chỉ có thể sử dụng tối đa một lần. Cũng biết rằng nếu tất cả các phép màu được sử dụng, mỗi đứa trẻ sẽ nhận tối đa $$$k$$$ viên kẹo.\u003c/p\u003e\u003cp\u003eKhông tốt cho trẻ em ăn quá nhiều kẹo, vì vậy mỗi đứa trẻ chỉ được ăn tối đa một viên kẹo, trong khi số kẹo còn lại sẽ được chia đều cho Mẹ và Bố của chúng. Vì vậy nếu một đứa trẻ sẽ nhận được một số lượng kẹo chẵn (có thể là không), thì chúng sẽ không thể ăn bất kỳ viên kẹo nào và sẽ buồn. Tuy nhiên, những đứa trẻ còn lại (nhận được một số lượng kẹo lẻ) sẽ vui vẻ.\u003c/p\u003e\u003cp\u003eGiúp Ông già Noel biết số lượng tối đa đứa trẻ mà ông có thể làm hạnh phúc bằng cách sử dụng một số phép màu của mình.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa ba số nguyên $$$n$$$, $$$m$$$, và $$$k$$$ ($$$1 \\leq n \\leq 100\\,000, 1 \\leq m \\leq 10^9, 1 \\leq k \\leq 8$$$)\u0026nbsp;— số lượng phép màu, số lượng trẻ em và giới hạn trên số kẹo mà một đứa trẻ có thể nhận nếu tất cả các phép màu được sử dụng, tương ứng.\u003c/p\u003e\u003cp\u003eSau đó là $$$n$$$ dòng, mỗi dòng chứa các số nguyên $$$L_i$$$ và $$$R_i$$$ ($$$1 \\leq L_i \\leq R_i \\leq m$$$)\u0026nbsp;— các tham số của phép màu thứ $$$i$$$.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn ra một số nguyên duy nhất\u0026nbsp;— số lượng tối đa đứa trẻ mà Ông già Noel có thể làm hạnh phúc.\u003c/p\u003e"}},{"title":"Ví dụ 1","value":{"format":"HTML","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\u003e3 5 3\n1 3\n2 4\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ đầu tiên, Ông già Noel nên áp dụng phép màu thứ nhất và thứ ba. Trong trường hợp này, tất cả trẻ em sẽ vui vẻ ngoại trừ đứa thứ ba.\u003c/p\u003e"}}]}