Workout

Time limit20sMemory limit1024 MB

Summary

Given a strictly increasing sequence and up to K inserted integers, minimize the largest gap between consecutive sessions.

Level: Medium6 of 10
Topics: Binary search, Greedy, Math, Implementation
Solved: No attempts yet

Problem

Tambourine has prepared a fitness program so that she can become more fit. The program is made of N sessions. During the i-th session, Tambourine will exercise for Mi minutes. The number of minutes she exercises in each session are strictly increasing.

The difficulty of her fitness program is equal to the maximum difference in the number of minutes between any two consecutive training sessions.

To make her program less difficult, Tambourine has decided to add up to K additional training sessions to her fitness program. She can add these sessions anywhere in her fitness program, and exercise any positive integer number of minutes in each of them. After the additional training sessions are added, the number of minutes she exercises in each session must still be strictly increasing. What is the minimum difficulty possible?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and K. The second line contains N integers, the i-th of these is Mi, the number of minutes she will exercise in the i-th session.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum difficulty possible after up to K additional training sessions are added.

Limits

1 ≤ T ≤ 100.
For at most 10 test cases, 2 ≤ N ≤ 105.
For all other test cases, 2 ≤ N ≤ 300.
1 ≤ Mi ≤ 109.
Mi < Mi+1 for all i.

Examples2

Example 1
Input
```
1
3 1
100 200 230
```
Expected output
```
Case #1: 50
```

Example 2

Input

3
5 2
10 13 15 16 17
5 6
9 10 20 26 30
8 3
1 2 3 4 5 6 7 10

Expected output

Case #1: 2
Case #2: 3
Case #3: 1