{"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\u003eサンタクロースになるのはとても難しいです。時には困難な状況に対処しなければなりません。\u003c/p\u003e\u003cp\u003e今日、サンタクロースは休暇にやってきて、$$$m$$$人の子供たちが前に並んでいました。彼らを$$$1$$$から$$$m$$$まで番号をつけましょう。サンタクロースは$$$n$$$つの呪文を知っています。第$$$i$$$の呪文は、$$$[L_i, R_i]$$$の範囲内にいる子供たちにキャンディを与えます。各呪文は最大1回使用できます。また、すべての呪文が使用された場合、各子供が最大$$$k$$$個のキャンディを受け取ることがわかっています。\u003c/p\u003e\u003cp\u003e子供たちがたくさんのお菓子を食べるのは良くないので、各子供は1つのキャンディしか食べることができません。残りのキャンディは彼(または彼女)のお母さんとお父さんの間で平等に分けられます。したがって、もし子供に偶数個のキャンディが与えられる場合(おそらくゼロも含む)、彼(または彼女)はどんなキャンディも食べることができず、悲しくなります。しかし、残りの子供たち(奇数個のキャンディを受け取った子供たち)は幸せになります。\u003c/p\u003e\u003cp\u003eサンタクロースがいくつの呪文を使って幸せにできる最大の子供の数を知るのを手伝ってください。\u003c/p\u003e"}},{"title":"入力","value":{"format":"HTML","content":"\u003cp\u003e最初の行には、呪文の数、子供の数、およびすべての呪文が使用された場合の子供が受け取れるキャンディの上限を表す整数$$$n$$$、$$$m$$$、$$$k$$$ ($$$1 \\leq n \\leq 100\\,000, 1 \\leq m \\leq 10^9, 1 \\leq k \\leq 8$$$) が含まれています。\u003c/p\u003e\u003cp\u003eこれに続いて、$$$n$$$行があり、各行には、呪文のパラメータを表す整数$$$L_i$$$と$$$R_i$$$ ($$$1 \\leq L_i \\leq R_i \\leq m$$$) が含まれています。\u003c/p\u003e"}},{"title":"出力","value":{"format":"HTML","content":"\u003cp\u003e1つの整数を出力してください。これは、サンタが幸せにできる最大の子供の数です。\u003c/p\u003e"}},{"title":"サンプル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":"注意","value":{"format":"HTML","content":"\u003cp\u003e最初の例では、サンタは最初と三番目の呪文を使用すべきです。この場合、三番目以外のすべての子供が幸せになります。\u003c/p\u003e"}}]}