Di dekat rumah besar Prof. Pang, terdapat koloni berisi $m$ semut yang tinggal di bawah tanah dalam sebuah gua dengan $n$ lubang. Mereka keluar melalui lubang-lubang itu untuk mencari makanan. Jadi, di manakah makanannya? Seharusnya ada di kulkas besar Prof. Pang. Para semut ingin mencuri makanan dari kulkas besar tersebut.

Secara khusus, seekor semut memerlukan 1 detik untuk keluar dari gua melalui lubang mana pun dan 1 detik untuk masuk melalui lubang mana pun. Lubang-lubang memiliki lokasi berbeda. Jarak antara lubang ke-$i$ dan kulkas adalah $a_i$. Jadi, setelah keluar melalui lubang ke-$i$, seekor semut memerlukan $a_i$ detik untuk menuju kulkas. Setelah mencuri makanan, semut memerlukan $a_i$ detik untuk kembali ke lubang ke-$i$. Mencuri makanan tidak memerlukan waktu karena para semut cukup terampil.

Setiap semut akan keluar dari gua untuk mencuri sesuatu dari kulkas dan kembali (masuk) ke gua setelah mencuri. Setiap semut harus keluar tepat sekali lalu kembali. Seekor semut bebas memilih satu lubang untuk keluar dan satu lubang untuk masuk; kedua lubang tidak harus sama. Untuk lubang mana pun, pada detik mana pun, paling banyak satu semut dapat keluar atau masuk gua melaluinya. Tidak boleh ada satu semut keluar dan semut lain masuk melalui lubang yang sama pada detik yang sama. Karena batas kapasitas ini, beberapa semut mungkin perlu menunggu sebelum keluar melalui lubang dan/atau sebelum kembali ke lubang setelah mencuri.

Jadi Anda, sahabat Prof. Pang, perlu menghitung biaya waktu minimum agar para semut mencapai tujuannya dan mengerjai Prof. Pang sehingga mereka bisa mencuri makanan tanpa tertangkap olehnya. Biaya waktu didefinisikan sebagai total panjang waktu ketika setidaknya satu semut tidak berada di dalam gua. Saat semut sedang masuk atau keluar melalui suatu lubang, semut tersebut dianggap tidak berada di dalam gua.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1\le T\le10^5$) yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi dua bilangan bulat $n,m$ ($1\le n\le10^5$, $1\le m\le10^{14}$) yang masing-masing menyatakan banyaknya lubang dan banyaknya semut. Baris kedua berisi $n$ bilangan bulat $a_1,a_2,\ldots,a_n$ ($1\le a_i\le10^9$) yang menyatakan waktu yang diperlukan untuk menuju kulkas dari lubang ke-$i$.

Dijamin bahwa jumlah $n$ untuk seluruh kasus uji tidak melebihi $5\times10^5$.

Keluaran

Untuk setiap kasus uji, cetak satu baris berisi satu bilangan bulat yang menyatakan biaya waktu minimum dalam detik.

Contoh

Masukan 1

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

Keluaran 1

6
9
4

Catatan

Pada kasus uji ketiga, semut memerlukan total 2 detik untuk keluar dan masuk gua melalui lubang pertama. Semut juga memerlukan 2 detik untuk pergi ke kulkas dan kembali ke lubang.