题目描述

火车的运行依赖于火车头。为预防火车头发生故障，火车站预备了 \(k\) 辆小型备用火车头，每辆备用火车头只能带动少量连续的车厢， 且必须要按原车厢的次序。现给出多节车厢的乘客数，计算当火车头发生故障时，\(k\) 辆备用火车头最多能运送多少乘客。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示测试数据组数；每组数据中，第一行为正整数 \(n(≤50000)、m\) 和 \(k(m×k<n,k≤10)\)，分别表示火车车厢总节数、备用火车头能带动的车厢数和备用火车头数；第二行为 \(n\) 个正整数 \(p_i(≤100)\)，分别表示每节车厢的人数。

输出格式

对于每组数据，输出一个正整数，表示备用火车头最多运送的乘客数。

样例1

输入样例1

2
5 2 2
10 20 40 5 20
7 2 3
35 40 50 10 30 45 60

输出样例1

85
240

样例解释

样例 \(1\) 中，一共有 \(5\) 节车厢，\(2\) 个备用火车头，每个备用火车头可以带动 \(2\) 节车厢，\(2\) 个备用火车头分别带动 \((20 40)(5 20)\),总人数是 \(85\)；样例 \(2\) 中，\(3\) 个备用火车头分别带动 \(（35，40）（50， 10）（45，60）\)，总人数是 \(240\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("locomotive.in","r",stdin);
freopen("locomotive.out","w",stdout);