Ginga Tetsudou no Penguin

题号：NC235478
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

https://www.bilibili.com/video/BV1kW41147uB

银河铁道上依次散布着 $n$ 只企鹅。

云浅希望能过从中选出 $k$ 只企鹅，帮助它们登上列车。

因为企鹅的体重不同，让每一只企鹅上车需要花费的钱数也不同。第 $i$ 只企鹅上车需要花费的钱数是 $a_i$ 。

云浅不希望太多的企鹅被落下，因此她要求每 $m$ 个相邻的企鹅中就至少要有一只企鹅被选中。

也就是说，对于每个 $i=1,2,\cdots,n-m+1$ ，在 $[i,i+m-1]$ 这段区间中至少存在一只企鹅被选上了列车。

云浅并没有多少钱，她想要你帮她求出最小的花费。保证存在至少一种可能的方案。

输入描述:

第一行一个正整数  表示数据组数。

对于每组数据：第一行三个正整数 。

第二行  个正整数 。

输出描述:

对于每组数据，输出一行一个正整数表示答案。

示例1

输入

复制

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

输出

复制

7
10

说明

对于第一组数据，选择第  只企鹅即可。

对于第二组数据，应当选择第  只企鹅。

备注:

对于  的数据，，存在一种可行的方案。