暂无测试数据。

DD 现在在打保龄球，她面前有 $n$ 个写有权值的瓶子，她现在有 $m$ 个保龄球，每一个的宽度都可以保证击倒连续的 $w$ 个瓶子。

她现在想知道，最优策略下她可以击倒的瓶子权值总和是多少，需要注意的是如果 DD 这次扔到的区间的瓶子已经有被击倒的，这次只会击倒原来这一区间中没有击倒的，他也可以选择将保龄球扔到两侧，这样这次可以击倒不到 $w$ 个，也可以干脆扔空，这一次一个也不会击倒。

输入格式

第一行一个整数 $t$ 表示测试组数

接下来 $t$ 组数据，每组数据的第一行一个三个整数分别表示 $n,m,w$

第二行 $n$ 个整数表示每个瓶子的权值 $a_i$

输出格式

输出击倒的瓶子权值总和是多少

数据规模与约定

对于 $30\%$ 的数据，$1 \leq n \leq 50$

对于 $60\%$ 的数据，$1 \leq n \leq 500$

对于 $100\%$ 的数据，$1 \leq t \leq 10,1 \leq n \leq 10000,1 \leq m \leq 500,1 \leq w \leq 100,-10000 \leq a_i \leq 10000$

1
9 3 3
2 8 -5 3 5 8 4 8 -6

38