{"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\u003eLYD有很多任务要做,最近他学会了一条新的时间管理法:如果一项任务不超过d分钟的时间,就立即完成。\n他有一个含n个任务的列表,第i个任务难度为pi,它需要pi分钟才能完成。\u003c/p\u003e\n\n\u003cp\u003eLYD按顺序逐个读取任务,如果任务难度不超过d,他就必须立即开始做这个任务。如果一项任务的难度大于d,他就不会做这项任务。\n然而他不能对任务列表重新排列,跳过任务不花任何时间。\u003c/p\u003e\n\n\u003cp\u003eLYD总共有t分钟来完成尽量多的任务,但他不想一直工作,于是他决定在连续做了m项任务后休息一下,休息时间与完成这m项任务所花费的总时间相同。\u003c/p\u003e\n\n\u003cp\u003e举个栗子,如果n\u003d7,p\u003d[3,1,4,1,5,9,2],d\u003d3和m\u003d2 LYD按以下步骤工作:\u003cbr\u003e\n1. LYD读取第一个任务,其难度不大于d(p1\u003d3≤d\u003d3),工作3分钟;\u003cbr\u003e\n2. LYD读取第二个任务,其难度不大于d(p2\u003d1≤d\u003d3),工作1分钟;\u003cbr\u003e\n3. LYD注意到他已经完成了m\u003d2个任务,并休息了3+1\u003d4分钟;\u003cbr\u003e\n4. LYD读取第三个任务,其难度大于d(p3\u003d4\u003ed\u003d3),并且不花任何时间跳过它;\u003cbr\u003e\n5. LYD读取第四个任务,其难度不大于d,工作1分钟;\u003cbr\u003e\n6. LYD读取任务5和任务6,跳过它们;\u003cbr\u003e\n7. LYD读取第7个任务,其难度不大于d,工作2分钟;\u003cbr\u003e\n8. LYD注意到他已经完成了m\u003d2个任务,并休息了1+2\u003d3分钟。\u003cbr\u003e\n\u003c/p\u003e\n\u003cp\u003eLYD在t分钟后停止,如果他已启动了一个任务,但此时尚未完成,则该任务不被视为已完成。允许在最后一个组中完成少于m个任务。\n另外,在最后一组任务结束后休息时间比需要的时间短是可以接受的,甚至根本没有休息时间——他的工作日结束了,无论如何他都有足够的时间休息。\u003c/p\u003e\n\n\u003cp\u003e请帮助LYD找到这样的值d,使得他在t分钟内完成任务数q达到最大。\u003c/p\u003e\n"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数T,表示测试组数。每组数据包含两行,第一行为三个整数n,m,t(1\u003c\u003dn\u003c\u003d2e5,1\u003c\u003dm\u003c\u003d2e5,1\u003c\u003dt\u003c\u003d4e10),\n分别代表任务总数,能够连续工作的最大任务数和总工作时间。第二行包含n个整数p1,p2,...,pn,代表每个任务的难度。\u003c/p\u003e\n\u003cp\u003e保证所有测试数据的n加起来不超过2e5\u003c/p\u003e\n"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e每个样例输出一行,每行两个整数q和d(1\u003c\u003dd\u003c\u003dt),q代表最大任务数。若d有多个满足条件,输出任意一个即可。\u003c/p\u003e\n"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4\u003cbr\u003e5 2 16\u003cbr\u003e5 6 1 4 7\u003cbr\u003e5 3 30\u003cbr\u003e5 6 1 4 7\u003cbr\u003e6 4 15\u003cbr\u003e12 5 15 7 20 17\u003cbr\u003e1 1 50\u003cbr\u003e100\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e3 5\u003cbr\u003e4 7\u003cbr\u003e2 10\u003cbr\u003e0 25\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e11 1 29\u003cbr\u003e6 4 3 7 5 3 4 7 3 5 3\u003cbr\u003e7 1 5\u003cbr\u003e1 1 1 1 1 1 1\u003cbr\u003e5 2 18\u003cbr\u003e2 3 3 7 5\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e4 3\u003cbr\u003e3 1\u003cbr\u003e4 5\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}