Minh Thư đang học lớp 10 chuyên tin tại trường THPT chuyên Hùng Vương, Minh Thư thường làm bài toán dạng dãy số chưa tốt, Minh Thư thường lo lắng mỗi khi thầy giáo cho các bài toán dạng này. Hôm nay, thầy giáo cho Minh Thư một bài toán dạng dãy số về nhà. Là một học sinh chăm học, Minh Thư muốn giải bài toán này, nếu không Minh Thư sẽ không có một giấc ngủ ngon vì suốt đêm em trằn trọc để suy nghĩ về bài toán.

Đề bài toán như sau: Cho số nguyên \(n\) và một dãy các số nguyên \(a_{1},\ a_{2},\ \ldots,\ a_{n}\). Bài toán yêu cầu Minh Thư tìm cách chia dãy số trên thành một số dãy con liên tiếp (vẫn giữ nguyên thứ tự) thỏa mãn điều kiện:

+ Tổng của các dãy con trên không lớn hơn số nguyên \(m\).

+ Tổng của các số lớn nhất trong các dãy con trên là nhỏ nhất.

Bạn hãy giúp Minh Thư giải bài toán này.

Giới hạn:

+ \(1 \leq n \leq 100000\)

+ \(0 \leq a_{i} \leq 10^{6}\)

+\(\ m \leq 2^{63}\)

Dữ liệu vào:

+ Dòng đầu chứa một số nguyên dương \(t\), là số test dữ liệu \((t\ \leq \ 5)\)

+ Với mỗi bộ dữ liệu, dòng tiếp theo chứa 2 số nguyên \(n,m\).

+ Dòng tiếp theo chứa \(n\) số nguyên của dãy \(a_{1},\ a_{2},\ \ldots,\ a_{n}\).

Kết quả:

+ Với mỗi bộ test, in ra một dòng duy nhất là tổng của các số lớn nhất trong dãy số trên. Nếu không có cách chia nào thỏa mãn điều kiện trên, hãy in ra \(- 1\).

Ví dụ:

Ràng buộc:

+ 20% test có \(a_{1},\ a_{2},\ \ldots,\ a_{n}\) là một dãy không giảm.

+ 30% test có \(n \leq 10000\)

+ 50% test còn lại không có ràng buộc gì thêm.