题目描述

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

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

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

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

输入格式

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

对于每组数据：

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

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

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

输出格式

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

样例

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

17
19