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 。

题目描述

Polycarp 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. Polycarp 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't spend any time for reading a task or skipping it. Polycarp 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. For example, if $ n=7 $ , $ p=[3, 1, 4, 1, 5, 9, 2] $ , $ d=3 $ and $ m=2 $ Polycarp works by the following schedule: - Polycarp reads the first task, its difficulty is not greater than $ d $ ( $ p_1=3 \le d=3 $ ) and works for $ 3 $ minutes (i.e. the minutes $ 1 $ , $ 2 $ , $ 3 $ ); - Polycarp reads the second task, its difficulty is not greater than $ d $ ( $ p_2=1 \le d=3 $ ) and works for $ 1 $ minute (i.e. the minute $ 4 $ ); - Polycarp notices that he has finished $ m=2 $ tasks and takes a break for $ 3+1=4 $ minutes (i.e. on the minutes $ 5, 6, 7, 8 $ ); - Polycarp reads the third task, its difficulty is greater than $ d $ ( $ p_3=4 > d=3 $ ) and skips it without spending any time; - Polycarp reads the fourth task, its difficulty is not greater than $ d $ ( $ p_4=1 \le d=3 $ ) and works for $ 1 $ minute (i.e. the minute $ 9 $ ); - Polycarp reads the tasks $ 5 $ and $ 6 $ , skips both of them ( $ p_5>d $ and $ p_6>d $ ); - Polycarp reads the $ 7 $ -th task, its difficulty is not greater than $ d $ ( $ p_7=2 \le d=3 $ ) and works for $ 2 $ minutes (i.e. the minutes $ 10 $ , $ 11 $ ); - Polycarp notices that he has finished $ m=2 $ tasks and takes a break for $ 1+2=3 $ minutes (i.e. on the minutes $ 12, 13, 14 $ ). Polycarp 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 — his working day is over and he will have enough time to rest anyway. Please help Polycarp to find such value $ d $ , which would allow him to complete maximum possible number of tasks in $ t $ minutes.

输入输出格式

输入格式

The first line of the input contains single integer $ c $ ( $ 1 \le c \le 5 \cdot 10^4 $ ) — 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. Each 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} $ ) — the number of tasks in Polycarp's 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 $ ) — difficulties of the tasks. The sum of values $ n $ for all test cases in the input does not exceed $ 2 \cdot 10^5 $ .

输出格式

Print $ c $ lines, each line should contain answer for the corresponding test case — 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.

输入输出样例

输入样例 #1

4
5 2 16
5 6 1 4 7
5 3 30
5 6 1 4 7
6 4 15
12 5 15 7 20 17
1 1 50
100

输出样例 #1

3 5
4 7
2 10
0 25

输入样例 #2

3
11 1 29
6 4 3 7 5 3 4 7 3 5 3
7 1 5
1 1 1 1 1 1 1
5 2 18
2 3 3 7 5

输出样例 #2

4 3
3 1
4 5

说明

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.