এবির এলাকায় শুধু সকাল ৬টা থেকে ৮টা পর্যন্তই পানি থাকে। তাই এবি সেই সময় পানি সংরক্ষণ করে রাখবে বলে চিন্তা করলো। কিন্তু পানি সংরক্ষণ করতে চাইলে এবির কিছু বালতি দরকার, ফলে, সে সুপারমার্কেটে বালতি রাখা হয় যেখানে সেখানে গেলো।
বালতি রাখার সেকশনে অনেকগুলো তাক ছিলো। বিভিন্ন তাকে বিভিন্ন মাপের বালতি রাখা ছিলো। একই তাকে রাখা বালতিগুলো একই মাপের ছিলো। এবি তাকগুলোর সাথে হেলান দেওয়া একটি মই দেখতে পেয়ে সেটি বেয়ে সবচেয়ে উপরের তাক পর্যন্ত উঠে গেলো। তারপর সে হঠাৎ সে বুঝতে পারলো সে এক হাতেই শুধু একটি বালতি ধরতে পারবে কারন অন্য হাতের সাহায্যে তার মই ধরতে এবং নামতে হবে। উল্লেখ্য এবি এক হাতে মই বেয়ে উঠার মত শক্তিশালী নয়। আর সে একবার মই বেয়ে নেমে যাওয়ার পর আর উঠতে পারবেনা কারণ আরো অনেকেই মইটি ব্যবহার করার জন্য অপেক্ষা করছে।
এবি হয়তো শক্তিশালী নয় কিন্তু সে বুদ্ধিমতি। সে এমন একটি উপায় বের করে ফেলল যাতে সে যত বেশি সম্ভব বালতি নিয়ে নিচে নামতে পারে আর তার একই সময়ে একটির বেশি বালতিও ধরতে না হয়।
Input
ইনপুটের প্রথম লাইনে একটি ইন্টিজার T, টেস্ট কেসের সংখ্যা দেওয়া থাকবে।
প্রত্যেক কেসে দুটি ইন্টিজার N,K তাকের সংখ্যা আর এবি সর্বোচ্চ মোট কত মাপের বালতি ধরতে পারে দেওয়া থাকবে। পরবর্তি লাইনে N-টি ইন্টিজার দেওয়া থাকবে যার i-তম ইন্টিজারটি হলো i-তম তাকে রাখা বালতির মাপ।
উল্লেখ্য যে, সবচেয়ে উপরের তাকটি হলো N-তম তাক তার নিচেরটি N-1 -তম তাক এভাবে সবচেয়ে নিচের তাকটি হলো ১ম তাক।
Output
প্রত্যেক টেস্টকেসের জন্য একটি লাইন “Case $X: Y” আউটপুট দিন যেখানে X হচ্ছে কেসের নম্বর আর Y হচ্ছে এবি সর্বোচ্চ কতটি বালতি নিতে পারবে সেটা।
Sample
| 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 |
প্রথম টেস্টকেসে, এবি তুলতে পারে
৯ম তাক থেকে 1 মাপের বালতি নিয়ে, ৮ম তাক এড়িয়ে নিচে নামবে
৭ম তাকে থেকে 2 মাপের বালতির ভেতর 1 মাপের বালতিটি রেখে 2 মাপের বালতিটি নিয়ে, ৬ষ্ঠ, ৫ম,৪র্থ এবং ৩য় তাক এড়িয়ে নিচে নামবে
২য় তাক থেকে 4 মাপের বালতির ভেতর 2 মাপের বালতিটি রেখে 4 মাপের বালতি নিয়ে নিচে নামবে
১ম তাক থেকে একই ভাবে 6 মাপের বালতি নিয়ে নিচে নামবে
মোট বালতি সংখ্যা 4. মোট মাপ = 1+3+4+6=14 ≤ K
২য় টেস্টকেসে, এবি তুলতে পারে
৫ম তাক থেকে 1 মাপের বালতি নিয়ে নিচে নামবে
৪র্থ তাক থেকে 2 মাপের বালতির ভেতর 1 মাপের বালতিটি রেখে 2 মাপের বালতিটি নিয়ে ৩য় তাক এড়িয়ে নিচে নামবে
একইভাবে ২য় তাক থেকে 3 মাপের বালতি নিয়ে ১ম তাক এড়িয়ে নিচে নামবে
মোট বালতি সংখ্যা 3. মোট মাপ = 1+2+3=6 ≤ K
