# Practice on Toph

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

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

In Abby’s area the water is available in the tap only from 6AM to 8AM. So, Abby thought she would store water during that time. But to store water Abby needs some buckets, thus, she went to the bucket section in the supermarket.

There were a lot of shelves in the bucket section. There were different sizes of buckets in different shelves. Every bucket in the same shelf has the same size. Abby saw a ladder leaning on the shelves and climbed up to reach the topmost shelf. After reaching the topmost shelf, she suddenly realized **she can hold only one bucket at a time on one hand** because she needs to use the other hand to hold on to the ladder and climb down. Note that, **she can not climb up using one hand** because she is not that strong and **once she climbs all the way down she can’t climb up the ladder again** cause a lot of people are waiting to use the ladder as well.

Abby might not be strong, but she is intelligent in deed. She thought of an idea using which she can pick as many buckets as possible in such a way that she won’t have to hold more than one bucket.

Remember as it was said before Abby is not much strong. As the larger the buckets are the heavier. So

First line of the input there is an integer **T**, the number of test cases.

In each test case, there are two integers **N,K**, the number of shelves and the maximum total size abby can hold. In the next line there are N integers i^{th} denotes the size of buckets on i^{th} shelf. Note that the 1st shelf is closest to the ground and the N-th bucket is the top most one.

0 ≤ K ≤200

0 < N ≤20

1 ≤ bucket size ≤ 100

Subtask #2 (30 points)

1 ≤ T ≤ 10

0 ≤ K ≤ 200

0 < N ≤ 100

1 ≤ bucket size ≤ 100

Subtask #3 (60 points)

1 ≤ T ≤ 1000

0 ≤ K ≤ 10

0 < N ≤10

1 ≤ bucket size ≤ 10

summation of all N among all test case doesn’t exceed 2x10

For each testcase output a line “**Case $X: Y**” where X is the case number and Y is the maximum number of buckets picked by Abby.

Input | Output |
---|---|

2 9 14 6 4 2 5 7 5 3 4 1 5 9 4 3 5 2 1 | Case $1: 4 Case $2: 3 |

In the 1st test case, Abby can pick

Bucket of size 1 from 9th shelf, skip 8th shelf and climb down

Put the Bucket of size 1 into the Bucket of size 3 and pick it up from 7th shelf, skip the 6th,5th,4th and 3rd shelves and climb down

Put the Bucket of size 3 into the Bucket of size 4 from 2nd shelf skip, pick it up, climb down

Put the Bucket of size 4 into the Bucket of size 6 from 1st shelf

Total number of buckets is 4. Total size=1+3+4+6=14 ≤ K

In the 2nd test case, Abby can pick

Bucket of size 1 from 5th shelf and climb down

Put the Bucket of size 1 into the bucket of size 2 from 4th shelf pick it up and skip 3rd shelf climb down

Put the Bucket of size 2 into the bucket of size 3 from 2nd shelf and climb down

Total number of buckets is 3. Total size=1+2+3=6 ≤ K

20% Solution Ratio

EgorKulikovEarliest,

EgorKulikovFastest, 0.6s

EgorKulikovLightest, 296 MB

EgorKulikovShortest, 21493B

Login to submit