Codeforces Round 760 (Div. 3) |
---|
Finished |
You are given an array $$$a$$$ of $$$n$$$ integers, and another integer $$$k$$$ such that $$$2k \le n$$$.
You have to perform exactly $$$k$$$ operations with this array. In one operation, you have to choose two elements of the array (let them be $$$a_i$$$ and $$$a_j$$$; they can be equal or different, but their positions in the array must not be the same), remove them from the array, and add $$$\lfloor \frac{a_i}{a_j} \rfloor$$$ to your score, where $$$\lfloor \frac{x}{y} \rfloor$$$ is the maximum integer not exceeding $$$\frac{x}{y}$$$.
Initially, your score is $$$0$$$. After you perform exactly $$$k$$$ operations, you add all the remaining elements of the array to the score.
Calculate the minimum possible score you can get.
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.
Each test case consists of two lines. The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$; $$$0 \le k \le \lfloor \frac{n}{2} \rfloor$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$).
Print one integer — the minimum possible score you can get.
5 7 3 1 1 1 2 1 3 1 5 1 5 5 5 5 5 4 2 1 3 3 7 2 0 4 2 9 2 1 10 10 1 10 2 7 10 3
2 16 0 6 16
Let's consider the example test.
In the first test case, one way to obtain a score of $$$2$$$ is the following one:
In the second test case, no matter which operations you choose, the resulting score is $$$16$$$.
In the third test case, one way to obtain a score of $$$0$$$ is the following one:
In the fourth test case, no operations can be performed, so the score is the sum of the elements of the array: $$$4 + 2 = 6$$$.
Name |
---|