{"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\u003eBerland regional ICPC contest has just ended. There were $$$m$$$ participants numbered from $$$1$$$ to $$$m$$$, who competed on a problemset of $$$n$$$ problems numbered from $$$1$$$ to $$$n$$$.\u003c/p\u003e\u003cp\u003eNow the editorial is about to take place. There are two problem authors, each of them is going to tell the tutorial to \u003cspan class\u003d\"tex-font-style-bf\"\u003eexactly $$$k$$$ consecutive tasks\u003c/span\u003e of the problemset. The authors choose the segment of $$$k$$$ consecutive tasks for themselves independently of each other. The segments can coincide, intersect or not intersect at all.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th participant is interested in listening to the tutorial of all consecutive tasks from $$$l_i$$$ to $$$r_i$$$. Each participant always chooses to listen to only the problem author that tells the tutorials to the maximum number of tasks he is interested in. Let this maximum number be $$$a_i$$$. No participant can listen to both of the authors, even if their segments don\u0027t intersect.\u003c/p\u003e\u003cp\u003eThe authors want to choose the segments of $$$k$$$ consecutive tasks for themselves in such a way that the sum of $$$a_i$$$ over all participants is maximized.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains three integers $$$n, m$$$ and $$$k$$$ ($$$1 \\le n, m \\le 2000$$$, $$$1 \\le k \\le n$$$)\u0026nbsp;— the number of problems, the number of participants and the length of the segment of tasks each of the problem authors plans to tell the tutorial to.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \\le l_i \\le r_i \\le n$$$)\u0026nbsp;— the segment of tasks the $$$i$$$-th participant is interested in listening to the tutorial to.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer\u0026nbsp;— the maximum sum of $$$a_i$$$ over all participants.\u003c/p\u003e"}},{"title":"Examples","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\u003e10 5 3\n1 3\n2 4\n6 9\n6 9\n1 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e10 3 3\n2 4\n4 6\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e4 4 1\n3 3\n1 1\n2 2\n4 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"}},{"title":"","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\u003e5 4 5\n1 2\n2 3\n3 4\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example the first author can tell the tutorial to problems from $$$1$$$ to $$$3$$$ and the second one\u0026nbsp;— from $$$6$$$ to $$$8$$$. That way the sequence of $$$a_i$$$ will be $$$[3, 2, 3, 3, 3]$$$. Notice that the last participant can\u0027t listen to both author, he only chooses the one that tells the maximum number of problems he\u0027s interested in.\u003c/p\u003e\u003cp\u003eIn the second example the first one can tell problems $$$2$$$ to $$$4$$$, the second one\u0026nbsp;— $$$4$$$ to $$$6$$$.\u003c/p\u003e\u003cp\u003eIn the third example the first one can tell problems $$$1$$$ to $$$1$$$, the second one\u0026nbsp;— $$$2$$$ to $$$2$$$. Or $$$4$$$ to $$$4$$$ and $$$3$$$ to $$$3$$$. Every pair of different problems will get the same sum of $$$2$$$.\u003c/p\u003e\u003cp\u003eIn the fourth example the first one can tell problems $$$1$$$ to $$$5$$$, the second one\u0026nbsp;— $$$1$$$ to $$$5$$$ as well.\u003c/p\u003e"}}]}