Xếp hộp

Cho $n$ hình chữ nhật, mỗi hình có chiều cao bằng $1$. Chiều rộng của mỗi hình chữ nhật là một lũy thừa của $2$ (nghĩa là có thể biểu diễn dưới dạng $2^x$ với $x$ là số nguyên không âm).

Bạn được cho một hộp hai chiều có chiều rộng $W$. Lưu ý $W$ không nhất thiết là lũy thừa của $2$, nhưng đảm bảo $W$ không nhỏ hơn chiều rộng của hình chữ nhật lớn nhất.

Hãy tìm chiều cao nhỏ nhất của hộp sao cho có thể xếp tất cả $n$ hình chữ nhật vào trong. Cho phép để khoảng trống trong hộp sau khi xếp.

Không được phép xoay các hình chữ nhật. Hai hình chữ nhật khác nhau không được phép giao nhau (diện tích giao bằng $0$).

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ:
  • Dòng đầu chứa hai số nguyên $n$ và $W$.
  • Dòng thứ hai chứa $n$ số nguyên $w_1,w_2,\dots ,w_n$ — chiều rộng của các hình chữ nhật. Mỗi $w_i$ là một lũy thừa của $2$.

Dữ liệu ra

In ra $t$ dòng, mỗi dòng là chiều cao nhỏ nhất của hộp tương ứng với mỗi bộ dữ liệu.

Ràng buộc

• $1\le t\le 5·{10}^3$
• $1\le n\le {10}^5$
• $1\le W\le {10}^9$
• $1\le w_i\le {10}^6$ và $w_i$ là lũy thừa của $2$
• ${max}_i{w}_i\le W$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$

Ví dụ