HUST Monthly 2011.06.26 (Personal Contest)

From: 2011-06-26 14:30:00 To: 2011-06-26 17:30:00 Now: 2017-09-22 06:56:16 Status: Public

C - Tobor and Energy Stone

Time Limit: 1s Memory Limit: 128MB

Submissions: 205 Solved: 36
Description

Y.D.I’s lab has many slots, the slot which contains gadgets and is mentioned in Problem B is a kind of them. This time another row of slots appears.

Tobor’s life is maintained by energy, and more energy Tobor has, more happy Tobor feel. Y.D.I has many slots, each can contain many energy stones, and they stands in a row. These stones contains powerful energy, and Tobor want to get them very much. However, Y.D.I just give one stone to Tobor every day, because this is enough for Tobor’s daily life, and Y.D.I has write a program to guard the energy stones. The program can express as follow:

Every time of run, it checks some segments of slots, compare the total number of stones in this segment to the number of initial state, and if the number is not the same, Y.D.I will get an alert. Each segment is some adjacent slots, and it has an even number of slot, and the program choose them randomly.

Tobor knows all about it, every time she can use some of her M arms(Tobor has M arms - state in Problem B), to pick up some stones up, and put it down to any slot or appropriates it to herself. After Tobor’s action, the program will run. After checking, Tobor can start the next turn of action. The program will run every time after Tobor’s action, either.

Tobor is timid, so she want to know at least how many stones she can get without Y.D.I got any alert. Can you tell her?

Input

 

Multiple cases. First line contains two integers N and M, where N indicates the number of slots, and M indicates the number of arms Tobor has, 0 < N,M <= 50000. Next line contains N 32-bit non-negative integers, which indicates the number of stones in every slot.

Output

 

Print case number first. print the number of energy stones that Tobor can get at least. See Sample Output.

Sample Input
3 1
1 2 3
3 2
1 2 1
Sample Output
Case 1:
0
Case 2:
1
Hint

 

For more information, please download the problems in zip or pdf.

Any question please mail to dy0013@163.com.

Source
idy0013@gmail.com