Gần ngôi nhà lớn của giáo sư Pang có một đàn gồm $m$ con kiến sống dưới lòng đất trong một hang có $n$ cửa. Chúng ra khỏi các cửa để tìm thức ăn. Vậy thức ăn ở đâu? Hẳn là trong chiếc tủ lạnh lớn của giáo sư Pang. Đàn kiến muốn lấy trộm thức ăn từ chiếc tủ lạnh đó.

Cụ thể, một con kiến cần 1 giây để ra khỏi hang qua bất kỳ cửa nào và 1 giây để vào hang qua bất kỳ cửa nào. Các cửa ở những vị trí khác nhau. Khoảng cách giữa cửa thứ $i$ và tủ lạnh là $a_i$. Vì vậy, sau khi ra khỏi hang qua cửa thứ $i$, một con kiến cần $a_i$ giây để đến tủ lạnh. Sau khi lấy trộm thức ăn, nó cần $a_i$ giây để quay lại cửa thứ $i$. Việc lấy trộm thức ăn không tốn thời gian vì đàn kiến đủ khéo léo.

Mỗi con kiến sẽ ra khỏi hang để lấy trộm thứ gì đó từ tủ lạnh rồi trở về (đi vào) hang sau khi lấy trộm. Mỗi con phải ra khỏi hang đúng một lần rồi trở về. Nó có thể tùy ý chọn một cửa để ra và tùy ý chọn một cửa để vào; hai cửa không nhất thiết phải giống nhau. Với bất kỳ cửa nào, trong bất kỳ giây nào, có nhiều nhất một con kiến đi ra hoặc đi vào hang qua cửa đó. Không thể có một con đi ra và một con khác đi vào cùng một cửa trong cùng một giây. Do giới hạn khả năng thông qua này, một số con có thể phải chờ trước khi ra qua cửa và/hoặc trước khi quay lại cửa sau khi lấy trộm.

Vì vậy, bạn, người bạn tốt của giáo sư Pang, cần tính thời gian tối thiểu để đàn kiến đạt mục tiêu và trêu giáo sư, giúp đàn kiến lấy trộm thức ăn mà không bị ông bắt. Chi phí thời gian được định nghĩa là tổng độ dài thời gian mà ít nhất một con kiến không ở trong hang. Khi một con đang đi vào hoặc đi ra qua một cửa, nó được tính là không ở trong hang.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1\le T\le10^5$), là số lượng bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n,m$ ($1\le n\le10^5$, $1\le m\le10^{14}$), lần lượt là số cửa và số kiến. Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ ($1\le a_i\le10^9$), là thời gian cần để đến tủ lạnh từ cửa thứ $i$.

Đảm bảo tổng $n$ của tất cả các bộ dữ liệu không vượt quá $5\times10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên là chi phí thời gian tối thiểu, tính bằng giây.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6
9
4

Ghi chú

Trong bộ dữ liệu thứ ba, con kiến mất tổng cộng 2 giây để ra và vào hang qua cửa thứ nhất. Nó cũng mất 2 giây để đi đến tủ lạnh và quay lại cửa.