题目描述

塔沃节快到了，Libra 和 Rahn 决定享用家乡的传统美食：烤兔头。

桌上有 $n$ 盘烤兔头排成一排，从左到右编号 $1\sim n$，第 $i$ 个盘子里有 $a_i$ 个烤兔头。经过商量，Libra 和 Rahn 决定各自从桌子的两端同时开始吃烤兔头，Libra 从左往右吃，Rahn 从右往左吃，两人吃兔头的速度相等，且都会先将当前的盘子内的烤兔头吃完后再吃下一盘，吃完的盘子会被后勤立刻撤走。由于 Libra 和 Rahn 还邀请了一些好友来品尝美食，所以当两人开始吃烤兔头前或吃完一个烤兔头后发现桌下只剩下 $\le k$ 盘烤兔头时会同时停止，剩余的烤兔头等好友们赴宴后再共同享用。

晚宴正在筹备的过程中，而 Libra 已经迫不及待的想要知道自己能吃多少烤兔头。你能帮 Libra 算出她能够吃到多少烤兔头吗？

输入

输入第一行一个整数 $T$，表示数据组数。

对于每组数据第一行两个整数 $n,k(1\le k \le n\le 10^5)$，$n$ 表示桌上的盘子数，$k$ 的含义见题目描述。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，$a_i(1\le a_i\le 10^9)$ 表示从左到右第 $i$ 个盘子中的烤兔头数。

保证对于每个测试点，$\sum n\le 5\times 10^5$。

输出

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

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

2
9

子任务

对于 $20\%$ 的测试数据，满足 $n, a_i\le 100, \sum n \le 1000$。