{"problem":{"name":"Welcome to Tokyo!","description":{"content":"There are $M$ competitive programmers (kyopro-ers) numbered $1$ to $M$, who will visit Tokyo during the $N$ days starting today. Kyopro-er $i$ will stay in Tokyo from the $L_i$\\-th day through the $R_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"wtf22_day1_d"},"statements":[{"statement_type":"Markdown","content":"There are $M$ competitive programmers (kyopro-ers) numbered $1$ to $M$, who will visit Tokyo during the $N$ days starting today. Kyopro-er $i$ will stay in Tokyo from the $L_i$\\-th day through the $R_i$\\-th day ($1 \\leq L_i \\leq R_i \\leq N$).\nMaroon is planning dinner parties with them. If a dinner party is held on the $x$\\-th day ($1 \\leq x \\leq N$), he can make friends with all kyopro-ers $i$ with $L_i \\leq x \\leq R_i$.\nFor each $k=1,2,\\cdots,N$, solve the following problem.\n\n*   Find the maximum number of kyopro-ers Maroon can make friends with if he holds exactly $k$ dinner parties.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^6$\n*   $1 \\leq M \\leq 10^6$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_M$ $R_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"wtf22_day1_d","tags":[],"sample_group":[["3 3\n1 1\n1 2\n3 3","2\n3\n3\n\n*   $k=1$: If he holds a party on the $1$\\-st day, he can make friends with kyopro-ers $1$ and $2$.\n*   $k=2$: If he holds a party on the $1$\\-st and $3$\\-rd days, he can make friends with kyopro-ers $1$, $2$, and $3$.\n*   $k=3$: If he holds a party on the $1$\\-st, $2$\\-nd, and $3$\\-rd days, he can make friends with kyopro-ers $1$, $2$, and $3$."],["4 4\n1 1\n2 2\n3 3\n4 4","1\n2\n3\n4"],["3 6\n1 1\n1 2\n1 2\n2 3\n2 3\n3 3","4\n6\n6"],["20 15\n15 19\n1 8\n6 11\n3 11\n11 17\n6 6\n16 20\n7 11\n11 14\n2 19\n1 3\n7 7\n6 19\n14 15\n15 15","7\n11\n12\n13\n14\n15\n15\n15\n15\n15\n15\n15\n15\n15\n15\n15\n15\n15\n15\n15"]],"created_at":"2026-03-03 11:01:13"}}