{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e$m$ students, including Kazari, will take an exam tomorrow.\u003cbr\u003eThe paper consists of exactly $n$ problems, the $i$-th problem contains $a_i$ correct answers and $b_i$ incorrect answers, i.e. the $i$-th problem contains $a_i + b_i$ candidates in total.\u003cbr\u003eEach student should choose exactly one candidate as answer for each problem. If the answer to a certain problem is correct, then the student will get one point. The student who gets the most points wins.\u003cbr\u003eStudents only know the structure of the paper, but they are able to talk with each other during the exam. \u003cb\u003eThey decide to choose a subset $S$ of all $n$ problems, and they will only be able to submit answers on these problems.\u003cbr\u003eThey want to know the maximum size of $S$ that the winner among them will solve all the problems in $S$ if they take the optimal strategy.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eFor sample $1$, students can choose $S \u003d \\{1\\}$,and we need at least $4$ students to guarantee the winner solve the only problem.\u003cbr\u003e\u003cbr\u003eFor sample $2$, students can choose $S \u003d \\{1, 2, 3\\}$, and we need at least $24$ students to guarantee the winner solve these three problems, but if $|S| \u003d 4$, we need at least $96$ students, which is more than $50$.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer $T$ $(1 \\le T \\le 100)$ denoting the number of test cases.\u003cbr\u003eEach test case starts with two integers $n, m$ $(1 \\le n \\le 100, 1 \\le m \\le 10 ^ 9)$, denoting the number of problems and the number of students. Each of next $n$ lines contains two integers $a_i, b_i$ (\u003cb\u003e$1 \\le b_i \\le 100, a_i \u003d 1$\u003c/b\u003e), indicating the number of correct answers and the number of incorrect answers of the $i$-th problem."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print an integer denoting the maximum size of $S$.\u003cbr\u003e"}},{"title":"Sample","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\u003e2\t\r\n3 5\r\n1 3\r\n1 3\r\n1 3\r\n5 50\r\n1 1\r\n1 3\r\n1 2\r\n1 3\r\n1 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}