운동

Tambourine은 체력을 더 기르기 위해 운동 프로그램을 준비했다! 이 프로그램은 N개의 세션으로 이루어진다. i번째 세션 동안 Tambourine은 $M_{i}$분 동안 운동한다. 각 세션에서 운동하는 시간(분)은 엄격히 증가한다.

운동 프로그램의 난이도는 연속한 임의의 두 훈련 세션 사이의 운동 시간(분) 차이 중 최댓값과 같다.

프로그램의 난이도를 낮추기 위해 Tambourine은 운동 프로그램에 추가 훈련 세션을 최대 K개 넣기로 했다. 이 세션들은 운동 프로그램의 어느 위치에나 넣을 수 있으며, 각 세션에서 임의의 양의 정수만큼의 분 동안 운동할 수 있다. 추가 훈련 세션을 넣은 뒤에도 각 세션에서 운동하는 시간(분)은 여전히 엄격히 증가해야 한다. 가능한 난이도의 최솟값은 얼마인가?

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 최대 10개의 테스트 케이스에 대해, 2 ≤ N ≤ $10^{5}$. 그 외 모든 테스트 케이스에 대해, 2 ≤ N ≤ 300. 1 ≤ $M_{i}$ ≤ $10^{9}$. 모든 i에 대해 $M_{i}$ < $M_{i+1}$이다.

테스트 세트 1

K = 1.

테스트 세트 2

1 ≤ K ≤ $10^{5}$.

입력의 첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 K가 포함된 한 줄로 시작한다. 둘째 줄에는 N개의 정수가 주어지며, 이 중 i번째 정수인 $M_{i}$는 i번째 세션에서 운동할 시간(분)이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호(1부터 시작)이고, y은 추가 훈련 세션을 최대 K개 넣은 뒤 가능한 난이도의 최솟값이다.

예제 케이스 #1에서 Tambourine은 세션을 최대 하나 추가할 수 있다. 추가된 세션은 굵게 표시되어 있다: 100 150 200 230. 이제 난이도는 50이다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서 Tambourine은 세션을 최대 둘 추가할 수 있다. 추가된 세션은 굵게 표시되어 있다: 10 12 13 14 15 16 17. 이제 난이도는 2이다.

예제 케이스 #2에서 Tambourine은 세션을 최대 여섯 추가할 수 있다. 추가된 세션은 굵게 표시되어 있다: 9 10 12 14 16 18 20 23 26 29 30. 이제 난이도는 3이다.

예제 케이스 #3에서 Tambourine은 세션을 최대 셋 추가할 수 있다. 추가된 세션은 굵게 표시되어 있다: 1 2 3 4 5 6 7 8 9 10. 이제 난이도는 1이다. Tambourine은 세션을 둘만 추가했다는 점에 유의하라.

참고: 이전 대회들과 달리, Kick Start 2020에서는 모든 테스트 세트가 결과가 공개되는 테스트 세트이므로 제출 즉시 피드백을 받는다.