{"trustable":true,"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\u003ePolycarp has a lot of work to do. Recently he has learned a new time management rule: \"if a task takes five minutes or less, do it immediately\". Polycarp likes the new rule, however he is not sure that five minutes is the optimal value. He supposes that this value $$$d$$$ should be chosen based on existing task list.\u003c/p\u003e\u003cp\u003ePolycarp has a list of $$$n$$$ tasks to complete. The $$$i$$$-th task has difficulty $$$p_i$$$, i.e. it requires exactly $$$p_i$$$ minutes to be done. Polycarp reads the tasks one by one from the first to the $$$n$$$-th. If a task difficulty is $$$d$$$ or less, Polycarp starts the work on the task immediately. If a task difficulty is strictly greater than $$$d$$$, he will not do the task at all. It is not allowed to rearrange tasks in the list. Polycarp doesn\u0027t spend any time for reading a task or skipping it.\u003c/p\u003e\u003cp\u003ePolycarp has $$$t$$$ minutes in total to complete maximum number of tasks. But he does not want to work all the time. He decides to make a break after each group of $$$m$$$ consecutive tasks he was working on. The break should take the same amount of time as it was spent in total on completion of these $$$m$$$ tasks.\u003c/p\u003e\u003cp\u003eFor example, if $$$n\u003d7$$$, $$$p\u003d[3, 1, 4, 1, 5, 9, 2]$$$, $$$d\u003d3$$$ and $$$m\u003d2$$$ Polycarp works by the following schedule:\u003c/p\u003e\u003cul\u003e \u003cli\u003e Polycarp reads the first task, its difficulty is not greater than $$$d$$$ ($$$p_1\u003d3 \\le d\u003d3$$$) and works for $$$3$$$ minutes (i.e. the minutes $$$1$$$, $$$2$$$, $$$3$$$); \u003c/li\u003e\u003cli\u003e Polycarp reads the second task, its difficulty is not greater than $$$d$$$ ($$$p_2\u003d1 \\le d\u003d3$$$) and works for $$$1$$$ minute (i.e. the minute $$$4$$$); \u003c/li\u003e\u003cli\u003e Polycarp notices that he has finished $$$m\u003d2$$$ tasks and takes a break for $$$3+1\u003d4$$$ minutes (i.e. on the minutes $$$5, 6, 7, 8$$$); \u003c/li\u003e\u003cli\u003e Polycarp reads the third task, its difficulty is greater than $$$d$$$ ($$$p_3\u003d4 \u0026gt; d\u003d3$$$) and skips it without spending any time; \u003c/li\u003e\u003cli\u003e Polycarp reads the fourth task, its difficulty is not greater than $$$d$$$ ($$$p_4\u003d1 \\le d\u003d3$$$) and works for $$$1$$$ minute (i.e. the minute $$$9$$$); \u003c/li\u003e\u003cli\u003e Polycarp reads the tasks $$$5$$$ and $$$6$$$, skips both of them ($$$p_5\u0026gt;d$$$ and $$$p_6\u0026gt;d$$$); \u003c/li\u003e\u003cli\u003e Polycarp reads the $$$7$$$-th task, its difficulty is not greater than $$$d$$$ ($$$p_7\u003d2 \\le d\u003d3$$$) and works for $$$2$$$ minutes (i.e. the minutes $$$10$$$, $$$11$$$); \u003c/li\u003e\u003cli\u003e Polycarp notices that he has finished $$$m\u003d2$$$ tasks and takes a break for $$$1+2\u003d3$$$ minutes (i.e. on the minutes $$$12, 13, 14$$$). \u003c/li\u003e\u003c/ul\u003e\u003cp\u003ePolycarp stops exactly after $$$t$$$ minutes. If Polycarp started a task but has not finished it by that time, the task is not considered as completed. It is allowed to complete less than $$$m$$$ tasks in the last group. Also Polycarp considers acceptable to have shorter break than needed after the last group of tasks or even not to have this break at all\u0026nbsp;— his working day is over and he will have enough time to rest anyway.\u003c/p\u003e\u003cp\u003ePlease help Polycarp to find such value $$$d$$$, which would allow him to complete maximum possible number of tasks in $$$t$$$ minutes.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains single integer $$$c$$$ ($$$1 \\le c \\le 5 \\cdot 10^4$$$)\u0026nbsp;— number of test cases. Then description of $$$c$$$ test cases follows. Solve test cases separately, test cases are completely independent and do not affect each other.\u003c/p\u003e\u003cp\u003eEach test case is described by two lines. The first of these lines contains three space-separated integers $$$n$$$, $$$m$$$ and $$$t$$$ ($$$1 \\le n \\le 2 \\cdot 10^5, 1 \\le m \\le 2 \\cdot 10^5, 1 \\le t \\le 4 \\cdot 10^{10}$$$)\u0026nbsp;— the number of tasks in Polycarp\u0027s list, the number of tasks he can do without a break and the total amount of time Polycarp can work on tasks. The second line of the test case contains $$$n$$$ space separated integers $$$p_1, p_2, \\dots, p_n$$$ ($$$1 \\le p_i \\le 2 \\cdot 10^5$$$)\u0026nbsp;— difficulties of the tasks.\u003c/p\u003e\u003cp\u003eThe sum of values $$$n$$$ for all test cases in the input does not exceed $$$2 \\cdot 10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint $$$c$$$ lines, each line should contain answer for the corresponding test case\u0026nbsp;— the maximum possible number of tasks Polycarp can complete and the integer value $$$d$$$ ($$$1 \\le d \\le t$$$) Polycarp should use in time management rule, separated by space. If there are several possible values $$$d$$$ for a test case, output any of them.\u003c/p\u003e"}},{"title":"Examples","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\u003e4\n5 2 16\n5 6 1 4 7\n5 3 30\n5 6 1 4 7\n6 4 15\n12 5 15 7 20 17\n1 1 50\n100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3 5\n4 7\n2 10\n0 25\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\n11 1 29\n6 4 3 7 5 3 4 7 3 5 3\n7 1 5\n1 1 1 1 1 1 1\n5 2 18\n2 3 3 7 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4 3\n3 1\n4 5\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 of the first example $$$n\u003d5$$$, $$$m\u003d2$$$ and $$$t\u003d16$$$. The sequence of difficulties is $$$[5, 6, 1, 4, 7]$$$. If Polycarp chooses $$$d\u003d5$$$ then he will complete $$$3$$$ tasks. Polycarp will work by the following schedule:\u003c/p\u003e\u003cul\u003e \u003cli\u003e Polycarp reads the first task, its difficulty is not greater than $$$d$$$ ($$$p_1\u003d5 \\le d\u003d5$$$) and works for $$$5$$$ minutes (i.e. the minutes $$$1, 2, \\dots, 5$$$); \u003c/li\u003e\u003cli\u003e Polycarp reads the second task, its difficulty is greater than $$$d$$$ ($$$p_2\u003d6 \u0026gt; d\u003d5$$$) and skips it without spending any time; \u003c/li\u003e\u003cli\u003e Polycarp reads the third task, its difficulty is not greater than $$$d$$$ ($$$p_3\u003d1 \\le d\u003d5$$$) and works for $$$1$$$ minute (i.e. the minute $$$6$$$); \u003c/li\u003e\u003cli\u003e Polycarp notices that he has finished $$$m\u003d2$$$ tasks and takes a break for $$$5+1\u003d6$$$ minutes (i.e. on the minutes $$$7, 8, \\dots, 12$$$); \u003c/li\u003e\u003cli\u003e Polycarp reads the fourth task, its difficulty is not greater than $$$d$$$ ($$$p_4\u003d4 \\le d\u003d5$$$) and works for $$$4$$$ minutes (i.e. the minutes $$$13, 14, 15, 16$$$); \u003c/li\u003e\u003cli\u003e Polycarp stops work because of $$$t\u003d16$$$. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eIn total in the first test case Polycarp will complete $$$3$$$ tasks for $$$d\u003d5$$$. He can\u0027t choose other value for $$$d$$$ to increase the number of completed tasks.\u003c/p\u003e"}}]}