{"problem":{"name":"Destroyer Takahashi","description":{"content":"In a town divided into a grid with $N$ rows and $10^9$ columns, there are $N$ walls, numbered $1$ to $N$.   Wall $i$ ranges from the $L_i$\\-th column to the $R_i$\\-th column from the left in the $i$\\-","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc230_d"},"statements":[{"statement_type":"Markdown","content":"In a town divided into a grid with $N$ rows and $10^9$ columns, there are $N$ walls, numbered $1$ to $N$.  \nWall $i$ ranges from the $L_i$\\-th column to the $R_i$\\-th column from the left in the $i$\\-th row from the top. (See also the figure at Sample Input and Output $1$.)\nTakahashi has decided to destroy all $N$ walls.  \nWith his superhuman strength, his one punch can damage consecutive $D$ columns at once.\n\n*   More formally, he can choose an **integer** $x$ between $1$ and $10^9 - D + 1$ (inclusive) to damage all walls that exist (or partly exist) in the $x$\\-th through $(x + D - 1)$\\-th columns and are not yet destroyed.\n\nWhen a part of a wall is damaged, that whole wall will be destroyed by the impact of the punch.  \n(See also the figure at Sample Input and Output $1$.)\nAt least how many times does Takahashi need to punch to destroy all walls?\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq D \\leq 10^9$\n*   $1 \\leq L_i \\leq R_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $D$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_N$ $R_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc230_d","tags":[],"sample_group":[["3 3\n1 2\n4 7\n5 9","2\n\nThe figure below describes the arrangements of walls in Sample Input $1$.\n![image](https://img.atcoder.jp/ghi/b7b9e6741514f51c6c0aac924589c9d2.png)\nHe can destroy all walls with two punches, such as the following. (Below, $\\lbrack a, b \\rbrack$ denotes the range from the $a$\\-th through $b$\\-th columns.)\n\n*   First, punch $\\lbrack 2, 4 \\rbrack$. The walls existing in $\\lbrack 2, 4 \\rbrack$ ― Walls $1$ and $2$ ― are damaged and destroyed.\n*   Second, punch $\\lbrack 5, 7 \\rbrack$. The wall existing in $\\lbrack 5, 7 \\rbrack$ ― Wall $3$ ― is damaged and destroyed.\n\nIt is also possible to destroy all walls with two punches in this way:\n\n*   First, punch $\\lbrack 7, 9 \\rbrack$ to destroy Walls $2$ and $3$.\n*   Second, punch $\\lbrack 1, 3 \\rbrack$ to destroy Wall $1$."],["3 3\n1 2\n4 7\n4 9","1\n\nThe difference from Sample Input/Output $1$ is that Wall $3$ now covers $\\lbrack 4, 9 \\rbrack$, not $\\lbrack 5, 9 \\rbrack$.  \nIn this case, he can punch $\\lbrack 2, 4 \\rbrack$ to destroy all walls with one punch."],["5 2\n1 100\n1 1000000000\n101 1000\n9982 44353\n1000000000 1000000000","3"]],"created_at":"2026-03-03 11:01:13"}}