CINEMACON - Cinema Conundrum

Adorsho Ingreji Uccho Biddaloy has recently opened Media Studies department. Even though the name of the institute implies otherwise, it offers various courses on Bangla media too. As part of a course called Deshi Movie Analysis, the students of this department has to watch at least M minutes of movies that are being shown at various cinema halls across the city and submit their analysis report.

Nadim, a student of this department, thought it would be great at first. How many students get to watch movies for education, right? Wrong! He quickly found out how gravely mistaken he was seeing movie titles like “Toke Valobashtei Hobe” and “Matha Noshto”. He decides to do away with this task as fast as possible.

There are N cinema halls situated in a straight line (he lives in one of the most well planned cities in the world) one after another, each showing a different movie. His plan is to, given the length of each movie in minutes, select the least number of movies that will satisfy the M minutes of movie-watching requirement of the course. As he is lazy, he does not want to watch a movie in a hall and then go to a hall far away from the previous one to watch another movie. So, he decides to watch movies in halls so that the hall of a movie is situated next to the hall of the previous movie that he watched, if he watches multiple movies. A person can watch only one movie and only once at a hall any time he wishes. Once a person enters a hall, he cannot leave before finishing the movie.

As stated before, he is lazy and has asked you, his best friend, to help him. You are lazy too, but you are a good programmer. So you decide to write a program.

Input

Input begins with a line containing a single integer T (1<=T<=100), denoting the number of test cases. T test cases follow. Each test case begins with a line containing two integers N (1<=N<=10000) and M (0<=M<=10^9), denoting the number of cinema halls(and thus the number of movies) and the minimum movie-watching experience required by the course respectively. The next line contains N space separated positive integers denoting the length of movies in minutes shown in cinema halls from left to right. These integers will not exceed 10^5.

Output

For each test case, output a single line in the format Case X: Y, where X denotes the test case number and Y denotes the minimum number of movies Nadim has to watch in consecutive cinema halls so that he earns at least M minutes of movie-watching experience. If he cannot complete this task, Y should be -1.

Example

Input:
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Output:
Case 1: 2
Case 2: 3

Added by:imranziad
Date:2015-11-25
Time limit:0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB CS Fest 2015 (H.M. Mehrab)

hide comments
2017-11-15 01:00:40
Good question on a known algo, better time limit than most similar problems on SPOJ where AC in Python is impossible.
2017-03-28 19:50:22
easy one forget to print -1 ..and also try this test case
1
2 0
1 1
ans 0
2016-07-27 20:15:32
array element can be 0
hack test case
arr = {1,1,2,0}
sum = 4
most of WA sol will give 4.
Don't Go over Geekforgeek most of sol is incorrect. -_-

Last edit: 2016-07-27 21:21:41
2016-02-09 13:39:11 Abhay Jain
Why is it showing WA? Can anyone help?
Submission ID: 16254394
EDIT: Accepted :D

Last edit: 2016-02-09 16:52:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.