CUTSEQS Cắt dãy

Cho số nguyên N và một dãy số nguyên a₁, a₂, …, a_N. Nhiệm vụ của bạn là phải cắt dãy số trên thành một số dãy số (giữ nguyên thứ tự) thỏa mãn:

·        Tổng của mỗi dãy số 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 trên là nhỏ nhất.

Input:

·        Dòng đầu gồm 2 số nguyên N và M. (1 ≤ N ≤ 10⁵; M < 2⁶³)

·        Dòng thứ hai gồm N số nguyên của dãy a₁, a₂, …, a_N.(0 ≤ a_i ≤ 10⁶)

Output:Gồm một số duy nhất là tổng của các số lớn nhất trong các dãy số trên. Nếu không có cách cắt nào thỏa mãn hai điều kiện trên, in ra -1.

Input	Output	Giải thích
8 17 2 2 2 8 1 8 2 1	12	Cắt thành 3 dãy 2 2 2, 8 1 8, 2 1