CUTSEQS - Cắt dãy

Giới hạn
  • Thời gian: 0.11s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho số nguyên N và một dãy số nguyên a 1 , a 2 , …, 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.

Dòng thứ hai gồm N số nguyên của dãy a 1 , a 2 , …, a N .

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.

Example 

Input:
8 17
2 2 2 8 1 8 2 1

Output:
12

Giải thích: Cắt thành 3 dãy 2 2 2, 8 1 8, 2 1

Giới hạn:
1 ≤ N ≤ 100000.
0 ≤ ai ≤ 106.
M < 263.

  • Người up: cun