H	A Problemsetter Blind with Emotion
	Input	Standard Input
	Output	Standard Output

Once there was this great problemsetter whom we've heard of before. He was blind with emotion. Let's call him Emotional Blind for now, assuming no coincidence with any real person will occur. He was always so busy with emotions that he never had the time to take care of all the requests and persuasions and tantrums going on around him to throw a feast. Naturally, the people around him i.e. the problemsetters got irritated but nothing could change his emotions about not throwing a party. Then the great Sultan came into the scenario. The Sultan, like so many other times when he claimed to have found an error on some little this or that - for example data, found the error with the way the emotional problemsetter was treating his poor fellows and got very angry.

Now Emotional Blind started to get scared and thought that he should prepare some long lectures filled with different emotions to drive the other problemsetters away whenever they come with another of those feast requests. Each lecture should consist of N topics. For each of these N topics, you are given 5 integers - x, a, b, c and d. For a particular topic, Emotional Blind needs to lecture each problemsetter for x minutes. While the time duration is same for every problemsetter, the materials must be exclusive i.e. he can't use the same lecture content to more than one problemsetter, as the problemsetters are very collaborative creatures and believe in information sharing. So, if he needs to drive away S problemsetters, he needs content of x * S minutes on that topic. He can collect contents by reading books or wikipedia. It takes him a minutes to read each book (Being the great programmer as he is, he has written a program that helps him to read any book in exactly a minutes.) and he gets contents of length b minutes for this particular topic. On the other hand, he needs c minutes to read a single wikipedia article (with all the external links) and can gather d minutes' content from them. He may read as many books or articles as he wishes.

Now, Emotional Blind has a total of M minutes to research. Help him to find out the maximum number of problemsetters he can drive away.

Input

Input starts with an integer T, the number of test cases.

Each test case starts with a line with 2 integers N (1≤N≤1000) and M (1≤M≤10000000). N lines follow. Each of these lines contains 5 integers - x (1≤x≤1000), a(1≤a≤100), b(1≤b≤a), c(1≤c≤100) and d(1≤d≤c).

Output

For each test case, print the case number and then the maximum possible number of problemsetters Emotional Blind can drive away. Check sample output for exact format.

Sample Input	Sample Output
1 3 100 10 20 10 30 15 20 6 4 4 4 20 3 3 5 5	Case 1: 1