Chopping Carrots (Easy Version)
Contest: Codeforces Round 809 (Div. 2)
Difficulty rating: 1700
Tags: binary search, brute force, constructive algorithms, greedy, number theory

This is the easy version of the problem. The only difference between the versions is the constraints on $$$n$$$, $$$k$$$, $$$a_i$$$, and the sum of $$$n$$$ over all test cases. You can make hacks only if both versions of the problem are solved.

Note the unusual memory limit.

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, and an integer $$$k$$$.

The cost of an array of integers $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ is $$$$$$\max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).$$$$$$

Here, $$$\lfloor \frac{x}{y} \rfloor$$$ denotes the integer part of the division of $$$x$$$ by $$$y$$$. Find the minimum cost of an array $$$p$$$ such that $$$1 \le p_i \le k$$$ for all $$$1 \le i \le n$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 3000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \ldots \le a_n \le 3000$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.

Output format:
For each test case, print a single integer — the minimum possible cost of an array $$$p$$$ satisfying the condition above.

Constraints:
Time limit: 4.0 s
Memory limit: 64.0 MB

Note:
In the first test case, the optimal array is $$$p = [1, 1, 1, 2, 2]$$$. The resulting array of values of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ is $$$[4, 5, 6, 4, 5]$$$. The cost of $$$p$$$ is $$$\max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2$$$. We can show that there is no array (satisfying the condition from the statement) with a smaller cost.

In the second test case, one of the optimal arrays is $$$p = [12, 12, 12, 12, 12]$$$, which results in all $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ being $$$0$$$.

In the third test case, the only possible array is $$$p = [1, 1, 1]$$$.

Example input:
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3

Example output:
2
0
13
1
4
7
0

Editorial:
Let's iterate over integers $$$v = 0, 1, \ldots, a_1$$$. We'll construct an answer assuming that the minimum value of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ is at least $$$v$$$.
For all $$$1 \le i \le n$$$, we set $$$p_i = \min(k, \lfloor \frac{a_i}{v} \rfloor)$$$: the maximum value $$$p_i$$$ such that $$$1 \le p_i \le k$$$ and $$$v \le \lfloor \frac{a_i}{p_i} \rfloor$$$ (if $$$v = 0$$$ we can just set $$$p_i = k$$$)).
Now, we find the value of $$$\max\limits_{1 \le i \le n}(\lfloor\frac{a_i}{p_i}\rfloor ) - v$$$. This gives the answer when the minimum value of $$$\lfloor \frac{a_i}{p_i} \rfloor$$$ is $$$v$$$.
Finally, we compute this for all $$$0 \le v \le a_1$$$. This gives a $$$\mathcal{O}(n \cdot a_1)$$$ time solution per test case.