Phân chia túi hàng

Một đoàn xe chở hàng đang di chuyển qua một tuyến đường dài. Trên tuyến đường này có \(n\) trạm kiểm soát, được đánh số liên tục từ \(1\) đến \(n\) từ trái sang phải, trạm kiểm soát thứ \(i\) đang giữ một kiện hàng có trọng lượng \(a_{i}\) kg.

Để không bị CSGT phạt vì quá giới hạn trọng tải của xe, bạn không thể vận chuyển nhiều hơn \(s\) đơn vị hàng hóa trong một chuyến xe. Bạn cần chia số hàng hóa thành nhiều chuyến sao cho:

• Mỗi chuyến xe không chở quá \(s\) đơn vị hàng, và mỗi chuyến xe sẽ vận chuyển các kiện hàng nằm trên một đoạn liên tiếp các trạm kiểm soát.

• Chi phí vận chuyển của một chuyến xe phụ thuộc vào kiện hàng nặng nhất trong chuyến đó và số lượng kiện hàng có trong chuyến. Cụ thể hơn, chi phí vận chuyển một chuyến chính là tổng của trọng lượng kiện hàng lớn nhất và số lượng kiện hàng trong chuyến trừ \(1\).

• Tổng chi phí vận chuyển của toàn bộ đoàn xe phải được tối ưu sao cho nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(n, s\) \((1 \leq n \leq 2 \times 10^6, 1 \leq s \leq 10^{18})\) --- số lượng trạm kiểm soát và tải trọng tối đa của mỗi chuyến đi.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((1 \leq a_i \leq \min(s, 10^9))\) --- trọng lượng của kiện hàng cần vận chuyển tại mỗi trạm.

Output

In ra một số nguyên duy nhất --- tổng chi phí vận chuyển tối thiểu để hoàn thành nhiệm vụ.

Example

6 7
3 1 5 2 1 4

15

Scoring

• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 20\)
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 100\)
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 5000\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 2 \times 10^5\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n \leq 2 \times 10^6\).