{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 \u0026lt;\u003d N \u0026lt;\u003d 10,000) mud pools.\r\u003cbr\u003e\r\u003cbr\u003eFarmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely.\r\u003cbr\u003e\r\u003cbr\u003eGiven the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools."}},{"title":"Input","value":{"format":"HTML","content":"* Line 1: Two space-separated integers: N and L\r\u003cbr\u003e\r\u003cbr\u003e* Lines 2..N+1: Line i+1 contains two space-separated integers: s_i and e_i (0 \u0026lt;\u003d s_i \u0026lt; e_i \u0026lt;\u003d 1,000,000,000) that specify the start and end points of a mud pool along the road. The mud pools will not overlap. These numbers specify points, so a mud pool from 35 to 39 can be covered by a single board of length 4. Mud pools at (3,6) and (6,9) are not considered to overlap.\r\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"* Line 1: The miminum number of planks FJ needs to use."}},{"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\u003e3 3\r\n1 6\r\n13 17\r\n8 12\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n\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":"INPUT DETAILS:\r\u003cbr\u003e\r\u003cbr\u003eFJ needs to use planks of length 3 to cover 3 mud pools. The mud pools cover regions 1 to 6, 8 to 12, and 13 to 17.\r\u003cbr\u003e\r\u003cbr\u003eOUTPUT DETAILS:\r\u003cbr\u003e\r\u003cbr\u003eFJ can cover the mud pools with five planks of length 3 in the following way:\r\u003cbr\u003e\u003cpre\u003e 111222..333444555....\r\u003cbr\u003e .MMMMM..MMMM.MMMM....\r\u003cbr\u003e 012345678901234567890\u003c/pre\u003e"}}]}