题目描述

2026 丙午马年，某马术俱乐部需要在 \(n\) 天内从商城采购马匹所需的草料与器具，每天恰好购买一件商品，第 \(i\) 天的商品原价为 \(a_i\)。

商铺有一套特殊的折扣规则：

• 若第 \(i\) 天以原价购买商品，则接下来的 \(k\) 天内（即第 \(i+1\) 天到第 \(i+k\) 天）购买的商品可以享受半价优惠（可以选择不使用）。
• 每件商品至多享受一次半价优惠。

请你帮俱乐部算出购买全部商品的最小总花费。

输入格式

本题有多组测试数据。输入 \(T\ (1 \le T \le 10)\)，表示数据组数。

对于每组数据：

第一行输入两个整数 \(n, k\ (1 \le k \le n \le 10^5)\)，分别表示商品数量和折扣持续天数。

第二行输入 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\ (2 \le a_i \le 10^9)\)，表示每件商品的原价。

保证所有 \(a_i\) 为偶数，同时也保证所有数据的 \(n\) 的和不超过 \(10^5\)。

输出格式

对于每组数据，输出一行一个整数，表示最小总花费。

样例输入

2
5 2
2 6 6 6 6
5 2
2 4 6 8 10

样例输出

17
19