{"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":"HTML","content":"\u003cp\u003eBowen dreamed one night that he had become the boss and was paying his employees.\n\u003cp\u003eBowen\u0027s company has $n$($n$ is odd) employees, each of whom has a payroll range $l_i$ to $r_i$, and Bowen has a total of $s$ dollars to pay his employees.\n\u003cp\u003eBowen needs to pay his employees in a certain way in order to make them think he is a good boss, so that the median employee salary is the largest.\n\u003cul\u003e\n \u003cli\u003ethe median of the sequence $$$[1, 4, 2, 5,7]$$$ is $$$4$$$.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eBowen tells you about this thing in next day and wants you to help him solve the problem so that he can pay out wages in his next dream.\n\u003cp\u003e(It is guaranteed that Bowen have enough money to pay the minimum salary, $\\sum_{i \u003d 1}^n l_i$ $\\leq$ s)"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer $$$t$$$ ($$$1 \\le t \\le 2 \\cdot 10^5$$$) — the number of test cases.\u003c/p\u003e\n\u003cp\u003eThe first line of each query contains two integers $$$n$$$ and $$$s$$$ ($$$1 \\le n \u0026lt; 2 \\cdot 10^5$$$, $$$1 \\le s \\le 2 \\cdot 10^{14}$$$) — the number of employees and the amount of money Bowen have.\u003c/p\u003e\n\u003cp\u003eThe following $$$n$$$ lines of each query contain the information about employees. The $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \\le l_i \\le r_i \\le 10^9$$$).\u003c/p\u003e\n\u003cp\u003eIt is guaranteed that the sum of all $$$n$$$ over all queries does not exceed $$$2 \\cdot 10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print one integer — the maximum median salary that Bowen can obtain.\u003c/p\u003e"}},{"title":"Sample 1","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\n1 1337\n1 1000000000\n5 26\n6 8\n5 6\n2 4\n2 7\n4 4\n3 26\n1 4\n10 12\n10 11\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1337\n6\n11\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, you can distribute salaries as follows: $$$sal_1 \u003d 12, sal_2 \u003d 2, sal_3 \u003d 11$$$ ($$$sal_i$$$ is the salary of the $$$i$$$-th employee). Then the median salary is $$$11$$$.\u003c/p\u003e\n\u003cp\u003eIn the second test case, you have to pay $$$1337$$$ dollars to the only employee.\u003c/p\u003e\n\u003cp\u003eIn the third test case, you can distribute salaries as follows: $$$sal_1 \u003d 4, sal_2 \u003d 3, sal_3 \u003d 6, sal_4 \u003d 6, sal_5 \u003d 7$$$. Then the median salary is $$$6$$$.\u003c/p\u003e"}}]}