운동

탬버린은 더 건강해지기 위해 운동 계획을 세웠다. 이 계획은 N개의 세션으로 이루어져 있다. i번째 세션에서 탬버린은 Mi분 동안 운동한다. 각 세션의 운동 시간은 엄격히 증가한다.

운동 계획의 난이도는 연속한 두 세션의 운동 시간 차이 중 최댓값이다.

난이도를 낮추기 위해 탬버린은 계획에 최대 K개의 세션을 추가하기로 했다. 세션은 계획의 어느 위치에든 추가할 수 있고, 각 세션에서 양의 정수 분만큼 운동할 수 있다. 세션을 추가한 뒤에도 각 세션의 운동 시간은 엄격히 증가해야 한다. 가능한 최소 난이도는 얼마인가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 N과 K가 주어진다. 둘째 줄에는 N개의 정수가 주어지며, i번째 정수는 i번째 세션에서 운동할 시간 Mi이다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 최대 K개의 세션을 추가한 뒤 가능한 최소 난이도이다.

• 1 ≤ T ≤ 100.
• 최대 10개의 테스트 케이스에 대해 2 ≤ N ≤ 105.
• 나머지 모든 테스트 케이스에 대해 2 ≤ N ≤ 300.
• 1 ≤ Mi ≤ 109.
• 모든 i에 대해 Mi < Mi+1.