{"trustable":false,"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":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n 爱丽丝喜欢集邮。她现在在邮局买一些新邮票。\u003cbr\u003e\n世界上有各种各样的邮票;它们的编号是1到N。但是,邮票不是单独出售的;必须成套购买。有M套不同的邮票可供选择; 第i套包括编号从l\u003csub\u003ei\u003c/sub\u003e到r\u003csub\u003ei\u003c/sub\u003e的邮票 。同一枚邮票可能会出现在不止一套邮票中,而且可能在任何一套邮票中都找不到一枚或多枚邮票。\u003cbr\u003e\n所有套装的价格都是一样的;因为爱丽丝的预算有限,她最多只能买K套不同的邮票。爱丽丝最多能买到多少种不同的邮票?\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"输入从一行开始,其中包含一个整数T,即测试用例的数量。接下来是T测试用例。\n\u003cbr\u003e每个测试用例都以一行开始,其中包含三个整数:N、M和K:可用的不同类型邮票的数量、可用邮票集的数量,以及Alice可以购买的最大邮票集数量。\n\u003cbr\u003e这些行中的第i行表示第i个套邮票,包含两个整数li和ri,表示该套邮票中可用邮票数目的范围。\n1≤T≤100\u003cbr\u003e\n1≤K≤M\u003cbr\u003e\n1≤N,M≤2000\u003cbr\u003e\n1≤Li≤Ri≤N\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,输出一行包含“case #x: y”,其中x是测试用例号(从1开始),y是Alice可以得到的不同类型邮票的最大数量。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e2\n5 3 2\n3 4\n1 1\n1 3\n100 2 1\n1 50\n90 100\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003eCase #1: 4\nCase #2: 50\n\n \n \u003ci style\u003d\"font-size:1px\"\u003e \u003c/i\u003e\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cpre\u003e\n在示例案例1中,Alice可以购买第一套和第三套邮票,其中包含前四种邮票。注意,她得到了两份邮票3,但只有不同种类的邮票的数量的问题,而不是每一种邮票的数量。\n在示例案例2中,Alice可以购买第一套邮票,其中包含50种不同的邮票。\n \n \u003c/pre\u003e"}}]}