旅行 Lacy

題目敘述

從前有個叫 Lacy 的青蛙在準備一年一次的跳石頭大會考，大會考沒通過的青蛙就永遠沒辦法拿到畢業證書。然而 Lacy 同時也在準備別的科目的大會考，所以不希望花太多時間練習跳石頭。跳石頭比賽是這樣，在一條直線(正x軸)上放 N 顆石頭, 一開始站在最左端的石頭上, 大會考通過的標準就是要在小於等於 K 次的跳躍到達最右端的石頭。每次跳躍就是從一顆石頭跳到另一顆石頭，假設這兩顆石頭的座標差是 d ,需要大於等於 d 的最大彈跳力才有辦法完成這次的跳躍。已經知道了這次檢定的石頭分佈方式還有 K, Lacy 想要知道他的最大彈跳力至少要是多少才能通過這次的大會考。

輸入說明

輸入的第一行包含一個整數 $T(T\leq 20)$，代表接下來有 $T$ 個不同的大會考試場。對於每個試場有2行資料，第1行是 $N,K(2\leq N \leq 10000,1\leq K \leq N-1)$ , 第二行有 N 個嚴格遞增的正整數用空格分開 $x_1,x_2,...,x_n (x_i \leq 10^{18})$ 表示每個石頭的座標。

輸出說明

對於每個試場，輸出一行，表示最大彈跳力至少需要多少才能通過考試。

範例輸入

範例輸出

7
1

子題一[20%]

$ x_i = i $

子題二[30%]

$N \leq 100$ $ x_i \leq 1000 $

子題三[50%]

無額外限制

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 3