408398: GYM103114 B Bsueh- and Gold Medals

Hsueh- is about to gradute! Congratulations! Wish all of you a brilliant future like him!

Because of Hsueh-'s active performance in the ACM, his gold medals are too many to take home. So he has to choose some of them.

Hsueh- has only one box. To make it beautiful, he will stack up his gold medals as a tower, which means every gold medal must be putted on another gold medal except the bottom medal, and there will be exactly one gold medal on each layer. In order to make the tower stable, Hsueh- will choose an integer $$$p$$$, then the lower gold medal should be at least $$$p$$$ $$$cm^2$$$ larger than the gold medal right above it. In other words, if the sizes of the tower consists of $$$k$$$ gold medals from top to bottom are $$$s_1$$$, $$$s_2$$$, $$$s_3$$$, $$$\dots$$$, $$$s_k$$$, then $$$s_1 + p \leq s_2$$$, $$$s_2 + p \leq s_3$$$, etc.

Hsueh- has $$$n$$$ gold medals, the sizes are $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ $$$cm^2$$$, and they have the same height. The box can contain at most $$$m(m \leq n)$$$ gold medals. Now Hsueh- was wondering the maximal integer $$$p$$$ that can fill the box.

The first line contains one integer $$$T(1 \leq T \leq 100)$$$, which represents the number of test case.

For each test case, the first line consists of two integers $$$n$$$, $$$m(2 \leq n \leq 10^3$$$, $$$2 \leq m \leq n)$$$ — the number of gold medals Hsueh- has and the number of gold medals his box can contain.

The second line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n(1 \leq a_i \leq 10^6)$$$ — the sizes of $$$n$$$ gold medals.

For each test case, print the maximal integer $$$p$$$ that can fill the box.

3
4 2
1 2 3 4
6 3
1 1 2 2 3 3
6 2
1 10 100 10000 100000 1000000

3
1
999999