AT_abc456_f [ABC456F] Plan Holidays

Takahashi is trying to decide his schedule for $ N $ days. Initially, none of the days are holidays. He can repeat either of the following operations any number of times: - Choose an integer $ i $ between $ 1 $ and $ N $ , inclusive, and make day $ i $ a holiday. This operation costs $ A_i $ . - Choose an integer $ i $ between $ 2 $ and $ N-1 $ , inclusive, such that both day $ i-1 $ and day $ i+1 $ are already holidays, and make day $ i $ a holiday. This operation is free. Find the minimum total cost required to create a consecutive block of $ K $ or more holidays. $ T $ test cases are given; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Here, $ \mathrm{case}_i $ denotes the input for the $ i $ -th test case. Each test case is given in the following format: > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 For the first test case, a consecutive block of at least two holidays can be created by performing operations as follows: - Make day $ 2 $ a holiday using the first type of operation. This costs $ 1 $ . - Make day $ 4 $ a holiday using the first type of operation. This costs $ 1 $ . - Make day $ 3 $ a holiday using the second type of operation. This is free. The total cost of this sequence of operations is $ 2 $ . It is impossible to create a consecutive block of two or more holidays with a cost less than $ 2 $ , so output $ 2 $ . ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 1 \leq K \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - All input values are integers. - The sum of $ N $ over all test cases is at most $ 2\times 10^5 $ .