بالقرب من منزل الأستاذ Pang الكبير، توجد مستعمرة من $m$ نملة تعيش تحت الأرض في كهف له $n$ فتحة. تخرج النملات من الفتحات بحثًا عن الطعام. فأين الطعام؟ يُفترض أنه في ثلاجة الأستاذ Pang الكبيرة. تريد النملات سرقة الطعام من تلك الثلاجة.

على وجه التحديد، تحتاج النملة إلى ثانية واحدة لمغادرة الكهف عبر أي فتحة، وثانية واحدة لدخوله عبر أي فتحة. تقع الفتحات في أماكن مختلفة. المسافة بين الفتحة رقم $i$ والثلاجة هي $a_i$. لذا، بعد الخروج عبر الفتحة رقم $i$، تحتاج النملة إلى $a_i$ ثانية للوصول إلى الثلاجة. وبعد سرقة بعض الطعام، تحتاج إلى $a_i$ ثانية للعودة إلى الفتحة رقم $i$. لا تستغرق سرقة الطعام أي وقت لأن النملات ماهرات بما يكفي.

ستغادر كل نملة الكهف لسرقة شيء من الثلاجة، ثم تعود إلى الكهف وتدخله بعد السرقة. يجب أن تغادر كل نملة الكهف مرة واحدة بالضبط ثم تعود إليه. يمكنها اختيار فتحة للخروج وفتحة للدخول بحرية، وليس من الضروري أن تكونا الفتحة نفسها. بالنسبة إلى أي فتحة وفي أي ثانية، يمكن لنملة واحدة على الأكثر أن تغادر الكهف أو تدخله عبرها. لا يمكن أن تخرج نملة وتدخل أخرى عبر الفتحة نفسها خلال الثانية نفسها. بسبب قيد السعة هذا، قد تحتاج بعض النملات إلى الانتظار قبل الخروج عبر الفتحة و/أو قبل العودة إلى الفتحة بعد السرقة.

لذا، بصفتك صديقًا مقربًا للأستاذ Pang، عليك حساب أقل كلفة زمنية للنملات لتحقيق الهدف، وممازحة الأستاذ بحيث تتمكن النملات من سرقة الطعام دون أن يمسك بها. تُعرّف الكلفة الزمنية بأنها مجموع أطوال الفترات التي تكون فيها نملة واحدة على الأقل خارج الكهف. عندما تكون نملة بصدد الدخول أو الخروج عبر إحدى الفتحات، فإنها تُعد خارج الكهف.

الإدخال

يحتوي السطر الأول على عدد صحيح واحد $T$ ($1\le T\le10^5$) يدل على عدد حالات الاختبار.

لكل حالة اختبار، يحتوي السطر الأول على عددين صحيحين $n,m$ ($1\le n\le10^5$، $1\le m\le10^{14}$) يدلان على عدد الفتحات وعدد النملات على الترتيب. يحتوي السطر الثاني على $n$ عددًا صحيحًا $a_1,a_2,\ldots,a_n$ ($1\le a_i\le10^9$) تدل على الزمن اللازم للوصول إلى الثلاجة من الفتحة رقم $i$.

من المضمون أن مجموع $n$ على جميع حالات الاختبار لا يتجاوز $5\times10^5$.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا يحتوي على عدد صحيح واحد يدل على أقل كلفة زمنية بالثواني.

أمثلة

الإدخال 1

3
2 4
1 2
3 10
1 2 3
5 1
1 2 3 4 5

الإخراج 1

6
9
4

ملاحظة

في حالة الاختبار الثالثة، تحتاج النملة إلى ثانيتين إجمالًا للخروج من الكهف والدخول إليه عبر الفتحة الأولى. وتحتاج إلى ثانيتين للذهاب إلى الثلاجة والعودة إلى الفتحة.