#P9667. [ICPC 2022 Jinan R] Tower

[ICPC 2022 Jinan R] Tower

题目描述

Prof. Pang built nn block towers with different heights. The ii-th tower has height aia_i.

Prof. Shou doesn't like these towers because of their arbitrary heights. He decides to first remove exactly m of them\textbf{first remove exactly \textit{m} of them}, and then perform some (or none) of the following operations:

  • Choose a tower and increase its height aia_i by 11.
  • Choose a tower and decrease its height aia_i by 11.
  • Choose a tower and divide its height aia_i by 22. If the new height is not an integer, it is rounded down.

Prof. Shou can never choose a removed tower. If after an operation, the height of a tower will become 00, that operation is not allowed. Under these constraints, Prof. Shou can perform an arbitrary number of operations in arbitrary order.

Prof. Shou would like all the towers that are not removed to have the same heights. Please calculate the minimum number of operations to achieve this.

输入格式

The first line contains one integer T (1T10)T~(1\le T \le 10), the number of test cases.

For each test case, the first line contains two integers n,m (1n500,0m<n)n, m~(1\le n\le 500, 0\le m <n), the number of towers, and the number of towers Prof. Shou should delete before performing the operations.

The next line contains nn integers a1,,an (1ai109)a_1,\ldots, a_n~(1\le a_i\le 10^9), the initial heights of the towers.

输出格式

For each test case, output the minimum number of operations in one line.

3
2 0
2 6
5 0
1 2 3 4 5
5 3
1 2 3 4 5
2
4
1