{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"在几千年前,Shamiko 的祖先 Lilith 抱着暗之一族征服世界的野望与光之一族决战,却被光之一族封印至今。现在,从封印中解脱出来的 Lilith 需要回复自己的力量。\n\nLilith 有 n 种属性值,并且 n 是一个奇数。Lilith 一共有 s 点点数可供分配,消耗 1 点数可以使得某种属性值加一。Lilith 希望将第 i 种属性值加到 l\u003csub\u003ei\u003c/sub\u003e 到 r\u003csub\u003ei\u003c/sub\u003e 之间(包含 l\u003csub\u003ei\u003c/sub\u003e 和 r\u003csub\u003ei\u003c/sub\u003e)。\n\n与此同时,Lilith 希望自己属性值的中位数尽可能大。现在,Shamiko 和 Chiyoda Momo 想要知道,Lilith 属性值的中位数的最大可能值是多少。\n\n众所周知,在数据有奇数个时,中位数就是把数据排序之后最中间的数。例如,[5, 1, 10, 17, 6] 的中位数是 6,[1, 2, 1] 的中位数是 1。\n\nShamiko 和 Chiyoda Momo 当然会这个问题,但 Shamiko 和 Chiyoda Momo 想考考你,所以 Shamiko 和 Chiyoda Momo 希望你能解决这个问题。\n\n由于 Nanako 也编不出来的原因,你需要回答 Shamiko 和 Chiyoda Momo 的 q 次询问。"}},{"title":"Input","value":{"format":"MD","content":"第一行包含一个整数 q (1 \u003c\u003d q \u003c\u003d 2 × 10\u003csup\u003e5\u003c/sup\u003e),代表共有 q 次询问。\n\n在每次询问中,第一行包含两个整数 n 和 s (1 \u003c\u003d n \u003c\u003d 2 × 10\u003csup\u003e5\u003c/sup\u003e, 1 \u003c\u003d s \u003c\u003d 2 × 10\u003csup\u003e14\u003c/sup\u003e),代表 Lilith 的属性值种类数量和可供 Lilith 分配的点数。输入数据保证 n 是一个奇数。\n\n接下来的 n 行每行包含两个整数 l\u003csub\u003ei\u003c/sub\u003e 和 r\u003csub\u003ei\u003c/sub\u003e (1 \u003c\u003d l\u003csub\u003ei\u003c/sub\u003e \u003c\u003d r\u003csub\u003ei\u003c/sub\u003e \u003c\u003d 10\u003csup\u003e9\u003c/sup\u003e),代表 Lilith 希望的第 i 种属性值的范围。\n\n输入数据保证 q 次询问中 n 的总和不超过 2 × 10\u003csup\u003e5\u003c/sup\u003e,且每次询问都有 s \u003e\u003d sigma(l\u003csub\u003ei\u003c/sub\u003e)。"}},{"title":"Output","value":{"format":"MD","content":"对于每组询问,输出一个整数,代表 Lilith 属性值的中位数的最大可能值。"}},{"title":"Example","value":{"format":"MD","content":"**Input**\n3\n3 26\n10 12\n1 4\n10 11\n1 1337\n1 1000000000\n5 26\n4 4\n2 4\n6 8\n5 6\n2 7\n\n**Output**\n11\n1337\n6"}},{"title":"Note","value":{"format":"MD","content":"在第一个样例中,Lilith 可能的分配方式为 a\u003csub\u003e1\u003c/sub\u003e \u003d 12, a\u003csub\u003e2\u003c/sub\u003e \u003d 2, a\u003csub\u003e3\u003c/sub\u003e \u003d 11。中位数是 11。\n\n在第二个样例中,Lilith 把所有 1337 点数都点了唯一的属性。\n\n在第三个样例中,Lilith 可能的分配方式为 a\u003csub\u003e1\u003c/sub\u003e \u003d 4, a\u003csub\u003e2\u003c/sub\u003e \u003d 3, a\u003csub\u003e3\u003c/sub\u003e \u003d 6, a\u003csub\u003e4\u003c/sub\u003e \u003d 6, a\u003csub\u003e5\u003c/sub\u003e \u003d 7。中位数是 6。"}}]}