কলু N সংখ্যক পাথরের স্তুপ নিয়ে খেলছিল। M সংখ্যক দানের মধ্যে সব গুলো স্তুপের পাথর সংখ্যা সমান করা তার লক্ষ্য।
সর্বোমোট স্তুপের সংখ্যা N, প্রতিটি স্তুপে পাথরের সংখ্যা এবং সর্বোচ্চ বৈধ দানের সংখ্যা M দেয়া থাকবে। সে নিজের ইচ্ছামত K এর একটি অঋণাত্মক মান নির্বাচন করতে পারবে। K এর সর্বনিম্ন যে মানের জন্য M সংখ্যক দানের মধ্যে সব স্তুপের পাথর সংখ্যা সমান করা সম্ভব সে মানটি নির্ণয় করতে হবে অথবা বলতে হবে সেটা অসম্ভব।
প্রথম লাইনে টেস্ট কেস সংখ্যা T দেয়া থাকবে।
প্রতিটি টেস্ট কেসের প্রথম লাইনে দুটি পূর্ণসংখ্যা N, M দেয়া থাকবে- কলুর কাছে সর্বমোট স্তুপ সংখ্যা, সর্বোচ্চ দান সংখ্যা এবং দ্বিতীয় লাইনে N সংখ্যক অঋণাত্মক পূর্ণসংখ্যা a1, .........., aN দেয়া থাকবে, যেখানে ai i-তম স্তুপে পাথর সংখ্যা নির্দেশ করে।
Subtask 1 (Up to 10 points):
$1 \le T \le 11$
$1 \le N \le 10$
$0 \le M \le 10$
$0 \le a_i \le 10$
Subtask 2 (Up to 30 points):
$1 \le T \le 11$
$1 \le N \le 500$
$0 \le M \le 500$
$0 \le a_i \le 500$
Subtask 3 (Up to 60 Points):
$1 \le T \le 11$
$1 \le N \le 10^5$
$0 \le M \le 10^9$
$0 \le a_i \le 10^9$
যদি সব গুলো স্তুপকে M সংখ্যক দানের মধ্যে সমান করা সম্ভব না হয় প্রিন্ট করতে হবে "-1" ( উদ্ধৃতি চিহ্ন ছাড়া), আর যদি সেটা সম্ভব হয় তবে K এর সর্বনিম্ন মান প্রিন্ট করতে হবে।
Input | Output |
---|---|
3 3 2 1 2 3 3 2 1 4 10 5 4 2 8 5 5 10 | 1 5 4 |