{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u003cimg align\u003d\"left\" height\u003d\"86\" src\u003d\"http://7xjob4.com1.z0.glb.clouddn.com/de6d31008c498d59e1bb45b74823ae94\" width\u003d\"291\"\u003e\u003cspan\u003eSamir\u003c/span\u003e returned home from the contest and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found a brush in his room which has width \u003cb\u003ew\u003c/b\u003e. Dusts are defined as \u003cspan\u003e2D\u003c/span\u003e points. And since they are scattered everywhere, \u003cspan\u003eSamir\u003c/span\u003e is a bit confused what to do. He asked \u003cspan\u003eSamee\u003c/span\u003e and found his idea. So, he attached a rope with the brush such that it can be moved horizontally (in \u003cb\u003eX\u003c/b\u003e axis) with the help of the rope but in straight line. He places it anywhere and moves it. For example, the \u003cb\u003ey\u003c/b\u003e co-ordinate of the bottom part of the brush is 2 and its width is 3, so the \u003cb\u003ey\u003c/b\u003e coordinate of the upper side of the brush will be 5. And if the brush is moved, all dusts whose \u003cb\u003ey\u003c/b\u003e co-ordinates are between 2 and 5 (inclusive) will be cleaned. After cleaning all the dusts in that part, \u003cspan\u003eSamir\u003c/span\u003e places the brush in another place and uses the same procedure. He defined a \u003cb\u003emove\u003c/b\u003e as placing the brush in a place and cleaning all the dusts in the horizontal zone of the brush.\u003c/p\u003e \n\u003cp\u003e You can assume that the rope is sufficiently large. Since \u003cspan\u003eSamir\u003c/span\u003e is too lazy, he doesn\u0027t want to clean all the room. Instead of doing it he thought that he would use at most \u003cb\u003ek\u003c/b\u003e moves. Now he wants to find the maximum number of dust units he can clean using at most \u003cb\u003ek\u003c/b\u003e moves. Please help him.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e Input starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e≤ 100)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e \n\u003cp\u003e Each case starts with a blank line. The next line contains three integers \u003cb\u003eN (1 ≤ N ≤ 100), w (1 ≤ w ≤ 10000)\u003c/b\u003e and \u003cb\u003ek (1 ≤ k ≤ 100)\u003c/b\u003e. \u003cb\u003eN\u003c/b\u003e means that there are N dust points. Each of the next \u003cb\u003eN\u003c/b\u003e lines contains two integers: \u003cb\u003e\u003cspan\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e \u003cspan\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e\u003c/b\u003e denoting the coordinates of the dusts. You can assume that \u003cb\u003e(-10\u003csup\u003e9\u003c/sup\u003e ≤ \u003cspan\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e, \u003cspan\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e)\u003c/b\u003e and all points are distinct.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e For each case print the case number and the maximum number of dusts \u003cspan\u003eSamir\u003c/span\u003e can clean using at most \u003cb\u003ek\u003c/b\u003e moves.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e3 2 1\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e0 0\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e20 2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e30 2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e\u0026nbsp;\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e3 1 1\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e0 0\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e20 2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e30 2\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eCase 1: 3\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eCase 2: 2\u003c/span\u003e\u003c/p\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e给你一个无限大的平面(2D)上面有N个\u003c/span\u003e 点,\u003cspan\u003e一个宽w的刷子,最多使用k次,每次使用只能横着水平刷一次。\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e问刷k次后刷过的地方最多可以覆盖多少个点。\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e数据都是整数。\u003c/span\u003e\u003c/p\u003e"}}]}