Sudden Tour!

Suppose waking up tomorrow morning you heard that there is no corona and your varsity is opened! At this wonderful news your friends planned a sudden tour to the highest peak of Bangladesh. Do you know the name? It’s Tazing dong(aka bijay).

As they are very excited they couldn’t decide what to take with them and what not to as their bag has a limited capacity of C. As you are the best programmer among your friends they asked for your help.In this problem you will be given a list of N items where the ith item takes a space of Si and a fun value of the ith item Fi set by your friends. They want to maximize the total fun value they can gain in this tour without overflowing their bag’s total capacity. They will be very disappointed at you if you don’t help them.

Input

On the first line you will be given the number of test cases T(T<11) on each test case you will be given the number of items N(0<N<=100) and the total capacity of the bag C(0<C<=100000). Each of the Next N lines will contain two positive integers Si and Fi not greater than 10000. You just have to print the desired answer in a single line.

Output

For each case print the case number and the maximum fun value In a single line.

Sample

Input	Output
2 3 10 9 2 5 8 2 3 2 15 9 8 8 9	Case 1: 11 Case 2: 9