A. 西坤丝 (sequence)

题目描述

Einniw 在西坤丝森林雇佣一队猎人为他打猎，他们共 $n$ 个人，每个人的打猎能力为 $a_i$，现在他们要组成一个队列。

为了避免在打猎过程中出现问题，对于给定的常数 $len,k$，将该队列的稳定度为： $$ \sum\limits_{i=1}^{n-len+1} \text{kthmax}(a[i:len]) $$ 其中 $\text{kthmax}(x)$ 为数组 $x$ 的第 $k$ 大值，$a[i:len]$ 表示数组 $a$ 从下标 $i$ 开始、长度为 $len$ 的一个子串。

现在，你可以任意重排这个队列，使得最终的稳定度最大，求出这个最大稳定度。

同时，在打猎过程中这个队列因种种原因极有可能会重新打乱，他们又想知道最坏情况下队列的情况。所以你还要求出任意重排这个队列所得到的最小稳定度是多少。

输入格式

本题多测。

第一行一个整数 $T$，表示数据组数。接下来共 $T$ 组数据，对于每一组数据：

第一行三个整数 $n,len,k$，含义如题目所述。第二行 $n$ 个整数，表示 $a_i$。

输出格式

对于 $T$ 组数据，每一组数据输出一行 $2$ 个数，表示最大和最小稳定度。

样例一

input

1
9 4 2
7 9 5 2 8 2 7 6 1

output

45 29

样例二

input

1
58 19 17
34 5 73 39 88 20 42 25 78 21 15 34 76 71 18 51 12 99 60 75 34 89 74 84 65 69 24 3 4 66 57 67 10 5 62 72 96 5 59 20 24 18 29 19 94 66 48 18 62 74 73 51 7 18 61 91 39 14

output

1579 264

样例三

见下发文件 $\texttt{ex\_sequence3.in/ans}$。

限制与约定

对于所有数据，$1\le T\le 5,1\le k\le len\le n,\sum n\le 3\times 10^5, 1\le a_i\le 10^9$。

时间限制： $1\texttt{s}$

空间限制： $512 \texttt{MiB}$