Một cuộc thi tìm kiếm vua đầu bếp được dự kiến sẽ diễn ra trên toàn quốc có rất nhiều thí sinh tham gia ở cả 3 miền Bắc, Trung, Nam. Ở vòng sơ loại ban tổ chức quyết định mỗi thí sinh sẽ lựa chọn bộ các món ăn trong ~N~ món ăn do ban tổ chức đưa ra. Món thứ ~i~ có thời gian nấu là ~t_i~, để nấu xong các món ăn của mình thì thời gian tối đa của mỗi thí sinh là thời gian của món lâu nhất. Một bộ các món ăn mà ban tổ chức đưa ra là các món ăn nằm cạnh nhau trong danh sách ~N~ món và có tổng thời gian nhỏ hơn ~S~ (phút). Nhưng vấn đề ở đây là số lượng thí sinh rất đông vì vậy ban tổ chức muốn có một phương án tối ưu để ghép bộ các món ăn đó sao cho tổng thời gian thực hiện các món ăn của các thí sinh là nhỏ nhất. Bạn hãy giúp ban tổ chức làm việc đó.

Yêu cầu: Tìm phương án chia các món ăn thành các bộ liên tiếp sao cho tổng thời gian thực hiện là nhỏ nhất.

Input

• Dòng đầu chứa 2 số nguyên ~N, S~ (~1 \le N \le 1000; 30 \le S \le 120~);
• Dòng thứ 2 là ~N~ số nguyên mỗi số là thời gian của một món ăn tương ứng ~t_i~ cách nhau bởi một dấu cách (~30 \le t_i \le 100~).

Output

• Gồm một dòng là tổng thời gian nhỏ nhất.

Sample Input 1

4 70
70 40 30 35

Sample Output 1

145