Một buổi tối, Youtuber_TWK vừa trải qua một cú thất tình và ngồi một mình trước máy tính, chẳng muốn làm gì.

Đúng lúc đó, doangiaphuc13 tìm đến.

doangiaphuc13 an ủi Youtuber_TWK:

"Thôi đời còn dài gái còn nhiều anh đừng buồn nữa mà. Nhưng mà em vừa tìm thấy cái này còn thú vị hơn nhiều!"

doangiaphuc13 từ từ lấy chiếc hộp cũ ra bên trên vẫn còn dòng chữ:
PROPERTY OF USSR - 1983

Youtuber_TWK tò mò mở chiếc hộp.

Bên trong là một thiết bị kỳ lạ. doangiaphuc13 nói rằng đây là một thiết bị thời gian được tìm thấy trong một kho đồ cũ.

Youtuber_TWK vốn đang thất tình nên quyết định thử vận may:

"Nếu quay lại được quá khứ thì có khi mọi chuyện đã khác."

doangiaphuc13 bật thiết bị.

"ẦM!"

Cả hai biến mất.

Khi tỉnh lại, họ phát hiện mình đang ở trên một đoàn tàu quân sự của Liên Xô. Đoàn tàu đang vận chuyển một hệ thống vũ khí bí mật, nhưng thiết bị thời gian đã bị hỏng.

Trên màn hình điều khiển xuất hiện một dãy gồm \(n\) toa tàu, đánh số từ \(1\) đến \(n\).

Mỗi toa \(i\) chứa một lượng năng lượng \(a_i\).

Để khởi động lại thiết bị thời gian, Youtuber_TWK và doangiaphuc13 phải lấy năng lượng từ một số toa.

Nếu họ chọn các toa:

\(i_1 < i_2 < ... < i_k\)

thì tổng năng lượng cần sử dụng là:

Trong đó:

• Lấy năng lượng từ toa \(i\) tiêu tốn \(a_i\) đơn vị năng lượng.
• Nếu bỏ qua \(d\) toa giữa hai toa được chọn liên tiếp, hệ thống phải tiêu tốn thêm \(d\) đơn vị năng lượng.
• Các toa trước toa đầu tiên và sau toa cuối cùng không tạo thêm chi phí.

Thiết bị chỉ cho phép sử dụng tối đa \(m\) đơn vị năng lượng.

Youtuber_TWK nhận ra rằng đây chính là cơ hội để quay lại thời điểm trước khi mình thất tình.

Nhưng doangiaphuc13 phát hiện một vấn đề nghiêm trọng.

Nếu sử dụng quá nhiều năng lượng, thiết bị sẽ không đủ năng lượng để đưa cả hai trở về hiện tại.

Vì vậy, hai người phải lựa chọn các toa tàu sao cho tổng giá trị năng lượng thu được là lớn nhất, nhưng tổng chi phí không được vượt quá \(m\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) — giá trị năng lượng của từng toa.

Output

• In ra một số nguyên duy nhất là giá trị lớn nhất có thể đạt được.

• Nếu không thể chọn toa nào, in ra 0.

Example

7 25
4 7 3 9 5 8 6

25

8 30
3 8 4 10 2 9 7 6

29

Ràng buộc

• \(1 \le n \le 2000\)
• \(1 \le m \le 10^5\)
• \(1 \le a_i \le 10^5\)

Scoring

• Subtask \(1\) (\(20%\) điểm): \(1 \le n \le 20,\ 1 \le m \le 100\).
• Subtask \(2\) (\(30%\) điểm): \(1 \le n \le 200,\ 1 \le m \le 5000\).
• Subtask \(3\) (\(50%\) điểm): \(1 \le n \le 2000,\ 1 \le m \le 10^5\).

Ngay sau đó, Youtuber_TWK đã nhanh chóng nhập kết quả vào hệ thống của máy.

BÍP

COMPLETE
RESTARTING THE SYSTEM
...
CALCULATING ENERGY REMAINING
...
CALCULATE FINISHED

Youtuber_TWK thở phào:

"Phù, cuối cùng cũng xong."

Câu chuyện vẫn chưa kết thúc!!!!

Chuyến đi vượt thời gian: Chapter II (Temporal Gate To 1962)