Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CUTSEQS - Cắt dãy

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

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.


Được gửi lên bởi:special_one
Ngày:2008-12-15
Thời gian chạy:0.110s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2019-03-16 02:17:10
tên tệp vào ra thường đặt tên là gì mấy bạn
2017-03-12 15:13:25
có 3 trường hợp có 1 trường hợp có 3 dòng có 1 dòng thiếu 3 dấu = làm mất 3 đấm :)
2014-11-14 15:52:58 [$Zeus$]
Làm thuật bựa bựa mà cũng 1 Phát AC mới ảo chứ :v :v Có vẻ test hơi yếu.
2013-09-21 04:14:23 Danh Nguyen
http://poj.org/problem?id=3017
2009-03-23 06:32:38 ntt
Bai nay kq -1 khi nao nhi. Co phai khi ton tai ai > M ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.