Limits 10s, 512 MB


কলু N সংখ্যক পাথরের স্তুপ নিয়ে খেলছিল। M সংখ্যক দানের মধ্যে সব গুলো স্তুপের পাথর সংখ্যা সমান করা তার লক্ষ্য।

  • একটি দানে সে দুইটি পাশাপাশি থাকা স্তুপ নির্বাচন করতে পারে, অর্থাৎ স্তুপ দুটি i-তম ও j-তম হলে |i-j|=1 । এরপর সে নির্বাচিত দুইটি স্তুপের মধ্যে সর্বোচ্চ K সংখ্যক পাথর বিনিময় করতে পারবে। সে একইরকম স্তুপের জোড়া যতবার খুশি নির্বাচন করতে পারবে।

সর্বোমোট স্তুপের সংখ্যা N, প্রতিটি স্তুপে পাথরের সংখ্যা এবং সর্বোচ্চ বৈধ দানের সংখ্যা M দেয়া থাকবে। সে নিজের ইচ্ছামত K এর একটি অঋণাত্মক মান নির্বাচন করতে পারবে। K এর সর্বনিম্ন যে মানের জন্য M সংখ্যক দানের মধ্যে সব স্তুপের পাথর সংখ্যা সমান করা সম্ভব সে মানটি নির্ণয় করতে হবে অথবা বলতে হবে সেটা অসম্ভব।

Input

প্রথম লাইনে টেস্ট কেস সংখ্যা T দেয়া থাকবে।

প্রতিটি টেস্ট কেসের প্রথম লাইনে দুটি পূর্ণসংখ্যা N, M দেয়া থাকবে- কলুর কাছে সর্বমোট স্তুপ সংখ্যা, সর্বোচ্চ দান সংখ্যা এবং দ্বিতীয় লাইনে N সংখ্যক অঋণাত্মক পূর্ণসংখ্যা a1, .........., aN দেয়া থাকবে, যেখানে ai i-তম স্তুপে পাথর সংখ্যা নির্দেশ করে।

Constraints:

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$

Output

যদি সব গুলো স্তুপকে M সংখ্যক দানের মধ্যে সমান করা সম্ভব না হয় প্রিন্ট করতে হবে "-1" ( উদ্ধৃতি চিহ্ন ছাড়া), আর যদি সেটা সম্ভব হয় তবে K এর সর্বনিম্ন মান প্রিন্ট করতে হবে।

Sample

InputOutput
3
3 2
1 2 3
3 2
1 4 10
5 4
2 8 5 5 10
1
5
4

Submit

Login to submit.

Statistics

80% Solution Ratio
DibyaJyotiEarliest, Jul '20
mbsabbirr127Fastest, 0.1s
riyad000Lightest, 918 kB
utsaroyShortest, 633B
Toph uses cookies. By continuing you agree to our Cookie Policy.