CF1070E Getting Deals Done

Polycarp有很多工作要做。最近他学会了一条新的时间管理技巧：“如果任务需要五分钟或更短时间，请立即执行”。Polycarp喜欢新技巧，但他不确定五分钟是最佳值。他认为这个值 d（分钟）应根据现有任务列表选择。 Polycarp有一份长度为 n 的要完成的任务清单。第 i 个任务有一个需要的时间Pi，即它确切地需要 Pi 分钟来完成。Polycarp从第一个到第 n 个逐个浏览任务。如果任务所需时间是 d 或更少，Polycarp立即开始执行任务。如果任务需要时间大于 d ，他不会去完成这个任务。列表中的任务的顺序是固定的了，所以，不容许你重新排序。当Polycarp阅读任务或跳过任务时，Polycarp不会花任何时间。 Polycarp有 T 分钟完成任务。但他不想一直工作。他决定在每做 m 个任务后休息一下。每次休息时间应该与完成这 m 个任务的时间相同。 例如，如果 N = 7，p = [3,1,4,1,5,9,2]，d = 3 和 m = 2 ，Polycarp的工作所需时间如下： Polycarp读取第一个任务，其难度不大于 d ，并使用了 3 分钟（即分钟 1， 2 ，3 ）; Polycarp读取第二项任务，其难度不大于 d ，并使用 1 分钟（即分钟 4 ）; Polycarp注意到他已经完成了 m = 2 个任务并休息 3 + 1 = 4 分钟（即分钟 5,6,7,8 ）; Polycarp读取第三项任务，其难度大于 d ，所以Polycarp不花任何时间跳过它; Polycarp读取第四项任务，其难度不大于 d ，并适用于 1 1分钟（即分钟 9 ）; Polycarp读取第五项和第六项任务，跳过他们两个。 Polycarp读取第七项任务，其难度不大于 d ，并使用 2 分钟（即分钟 10，11 ）;、 Polycarp注意到他又完成了 m = 2 个任务并休息 1 + 2 = 3分钟（即分钟 12,13,14 ）。 Polycarp会使用 T 分钟来完成任务。如果Polycarp启动任务但尚未完成任务，则该任务不会被视为已完成。 Polycarp认为在做完最后的任务之后可以接受比本来更短的休息时间，甚至根本没有休息——他的工作日结束了，他还有足够的时间休息。 请帮助Polycarp找到这样的价值 d ，使他能够在 T 分钟完成最多的任务。

输入的第一行包含单个整数 C （1≤ C ≤50000）表示数据组数。 对于每组数据，有两行。 第一行包含三个以空格分隔的整数 n ，m 和 T （1 ≤ n ≤200000，1≤ m ≤200000，1≤ T ≤40000000000） 测试用例的第二行包含 n 个整数（用空格分割），Pi表示每个任务所需时间（1≤ Pi ≤200000） ##### PS:所有 n 的总和不超过200000

输出 C 行，每行应包含对应数据的答案 - Polycarp可以完成的最大任务数 N 和整数值 d 。

In the first test case of the first example $ n=5 $ , $ m=2 $ and $ t=16 $ . The sequence of difficulties is $ [5, 6, 1, 4, 7] $ . If Polycarp chooses $ d=5 $ then he will complete $ 3 $ tasks. Polycarp will work by the following schedule: - Polycarp reads the first task, its difficulty is not greater than $ d $ ( $ p_1=5 \le d=5 $ ) and works for $ 5 $ minutes (i.e. the minutes $ 1, 2, \dots, 5 $ ); - Polycarp reads the second task, its difficulty is greater than $ d $ ( $ p_2=6 > d=5 $ ) and skips it without spending any time; - Polycarp reads the third task, its difficulty is not greater than $ d $ ( $ p_3=1 \le d=5 $ ) and works for $ 1 $ minute (i.e. the minute $ 6 $ ); - Polycarp notices that he has finished $ m=2 $ tasks and takes a break for $ 5+1=6 $ minutes (i.e. on the minutes $ 7, 8, \dots, 12 $ ); - Polycarp reads the fourth task, its difficulty is not greater than $ d $ ( $ p_4=4 \le d=5 $ ) and works for $ 4 $ minutes (i.e. the minutes $ 13, 14, 15, 16 $ ); - Polycarp stops work because of $ t=16 $ . In total in the first test case Polycarp will complete $ 3 $ tasks for $ d=5 $ . He can't choose other value for $ d $ to increase the number of completed tasks.