Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sudden Tour!

By Amateur · Limits 3s, 512 MB

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<=100) and the total capacity of the bag C(0<=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

InputOutput
2
3 10
9 2
5 8
2 3
2 15
9 8
8 9
Case 1: 11
Case 2: 9

    Discussion

    Statistics


    72% Solution Ratio

    Amd_SadiEarliest, 1M ago

    tstanvirFastest, 0.0s

    ashraful9194Lightest, 393 kB

    abid1729Shortest, 447B

    Submit

    Login to submit

    Editorial

    This is a classical 0-1 knapsack problem. Why we are calling it 0-1? Because if we want to take an i...

    Related Contests