{"problem":{"name":"Segment-Tree Optimization","description":{"content":"There is a sequence of $N$ terms, and $Q$ queries will be given on this sequence. The $i$\\-th query is for the interval $[L_i, R_i]$ (the interval $[a,b]$ is a set of integers between $a$ and $b$, inc","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc164_e"},"statements":[{"statement_type":"Markdown","content":"There is a sequence of $N$ terms, and $Q$ queries will be given on this sequence. The $i$\\-th query is for the interval $[L_i, R_i]$ (the interval $[a,b]$ is a set of integers between $a$ and $b$, inclusive).\nYou will answer this problem using a binary tree that satisfies the following conditions. Here, $i,j,k$ represent integers.\n\n*   Each node has an interval.\n*   The root node has the interval $[1, N]$.\n*   The node with the interval $[i, i]$ is a leaf. Also, the interval of a leaf can be represented as $[i,i]$.\n*   Each non-leaf node has exactly two children. Also, if the interval of a non-leaf node is $[i,j]$, the intervals of the children of this node are $[i,k]$ and $[k+1,j]$ ($i\\leq k<j$).\n\nIn this binary tree, when a query for the interval $[L,R]$ is given, a search is performed recursively according to the following rules.\n\n1.  Initially, the root is investigated.\n2.  When a node is investigated, if the interval of this node is included in $[L, R]$, its descendants are not investigated.\n3.  When a node is investigated, if the interval of this node have no intersection with $[L,R]$, its descendants are not investigated.\n4.  When a node is investigated, if neither 2. nor 3. applies, the two child nodes are investigated. (It can be shown that either 2. or 3. always applies to a leaf node.)\n\nWhen answering $Q$ queries, let $d$ be the maximum depth (distance from the root) of the investigated nodes, and $c$ be the total number of times nodes of depth $d$ are investigated. Here, if multiple nodes of depth $d$ are investigated in a single query, or if the same node is investigated in multiple queries, all those investigations count separately.\nYou want to design the binary tree to minimize $d$, and then to minimize $c$ while minimizing $d$. What are the values of $d$ and $c$ then?\n\n## Constraints\n\n*   $2\\leq N \\leq 4000$\n*   $1\\leq Q \\leq 10^5$\n*   $1\\leq L_i \\leq R_i \\leq N$ $(1\\leq i \\leq Q)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $Q$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_Q$ $R_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc164_e","tags":[],"sample_group":[["6 4\n2 3\n3 4\n2 4\n3 3","3 4\n\nWe have an interval $[1,6]$, and queries for the intervals $[2,3],[3,4],[2,4],[3,3]$. Here, if you use the binary tree shown in the figure below,\n\n*   for the first query, nodes $1,2,3,4,5$ are investigated, and the maximum depth among these is $2$ for nodes $4,5$;\n*   for the second query, nodes $1,2,3,4,5,6,7,8,9$ are investigated, and the maximum depth among these is $3$ for nodes $8,9$;\n*   for the third query, nodes $1,2,3,4,5,6,7$ are investigated, and the maximum depth among these is $2$ for nodes $4,5,6,7$;\n*   for the fourth query, nodes $1,2,3,4,5,8,9$ are investigated, and the maximum depth among these is $3$ for nodes $8,9$.\n\nTherefore, in this case, $d=3$, and nodes of depth $3$ were investigated four times ー nodes $8,9$ in the second query and nodes $8,9$ in the fourth query ー so $c=4$. In fact, this is an optimal method.\n(In the figure, the upper row shows the node number, and the lower row shows the interval of each node.)\n![image](https://img.atcoder.jp/arc164/c5776dc7ace92d9830788319820bed2d.png)"],["12 6\n1 10\n2 7\n3 6\n4 9\n5 8\n11 12","4 4"]],"created_at":"2026-03-03 11:01:13"}}