#A0005. 脸盆大哥(buhsi)

脸盆大哥(buhsi)

彩虹岛的木桶

时间限制:C/C++/Rust/Pascal 1秒,其他语言 2秒
空间限制:C/C++/Rust/Pascal 128M,其他语言 256M
64bit IO 格式:%lld

题目描述

彩虹岛网红脸盆大哥最骄傲的就是自己制作的木桶。一天,lwq 拿了 n 块木板,其中第 i 块木板的高度为 h_i。他希望脸盆大哥能够用这些木板制作出精美的木桶。

脸盆大哥告诉 lwq:

  • 制作一个木桶需要 k 块木板;
  • 所有桶的底面积固定为 s(底面的木板由 s 块木板组成,但不需要考虑具体组合方式,哪怕 1 块或 2 块木板也可以组成木桶,底面积仍为 s)。

lwq 想知道,用这些木板制作出来的木桶最多能够盛多少体积的水。

注意:木板不能重叠,且未使用的木板可以丢弃。

输入描述

第一行输入一个整数 T(2 ≤ T ≤ 20),表示共有 T 组测试数据。

对于每组测试数据:

  • 第一行输入三个整数 n, k, s(1 ≤ n, k, s ≤ 10^3),分别表示木板总数、每个木桶需要的木板数、木桶底面积。
  • 第二行输入 n 个整数 h_i(1 ≤ h_i ≤ 10^3),表示每块木板的高度。

输出描述

对于每组测试数据,输出一个整数 x,代表能装水的最大体积。

示例 1

2
4 2 5
1 2 3 4
5 2 5
1 4 5 2 3

text

20
30

说明

  • 第一组:第一个桶由高度 1、2 组成,盛水体积为 1×5=5;第二个桶由 3、4 组成,盛水体积为 3×5=15,总计 20。
  • 第二组:丢弃高度 1 的木板,剩余 (2,3) 和 (4,5) 组成两桶,最短板为 2 和 4,体积 = (2+4)×5 = 30。