{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eAlice likes to collect stamps. She is now at the post office buying some new stamps.\u003cbr\u003eThere are $N$ different kinds of stamps that exist in the world; they are numbered $1$ through $N$. However, stamps are not sold individually; they must be purchased in sets. There are $M$ different stamp sets available; the $i^{th}$ set contains the stamps numbered $L_i$ through $R_i$. The same stamp might appear in more than one set, and it is possible that one or more stamps are not available in any of the sets.\u003cbr\u003eAll of the sets cost the same amount; because Alice has a limited budget, she can buy at most $K$ different sets. What is the maximum number of different kinds of stamps that Alice can get?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input starts with one line containing one integer $T$, the number of test cases.$T$ test cases follow.\u003cbr\u003eEach test case begins with a line containing three integers: $N$, $M$, and $K$: the number of different kinds of stamps available, the number of stamp sets available, and the maximum number of stamp sets that Alice can buy.\u003cbr\u003e$M$ lines follow; the $i^{th} of these lines represents the $i^{th} stamp set and contains two integers, $L_i$ and $R_i$, which represent the inclusive range of the numbers of the stamps available in that set.\u003cbr\u003e$1 \\leq T \\leq 100$\u003cbr\u003e$1 \\leq K \\leq M$\u003cbr\u003e$1 \\leq N, M \\leq 2000$\u003cbr\u003e$1 \\leq L_i \\leq R_i \\leq N$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the maximum number of different kinds of stamp that Alice could get."}},{"title":"Sample","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\u003e2\r\n5 3 2\r\n3 4\r\n1 1\r\n1 3\r\n100 2 1\r\n1 50\r\n90 100\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 4\r\nCase #2: 50\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn sample case #1, Alice could buy the first and the third stamp sets, which contain the first four kinds\u003cbr\u003eof stamp. Note that she gets two copies of stamp 3, but only the number of different kinds of stamps\u003cbr\u003ematters, not the number of stamps of each kind.\u003cbr\u003eIn sample case #2, Alice could buy the first stamp set, which contains 50 different kinds of stamps.\u003cbr\u003e"}}]}