Chi phí

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
CaiWinDao
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho dãy số nguyên \(a_1\), \(a_2\),..., \(a_N\). Ở mỗi thao tác ta có thể chọn một phần tử nguyên dương trong dãy và giảm nó xuống \(1\) đơn vị. Hãy lập trình tính số thao tác tối thiểu cần thực hiện để mọi cặp phần tử liên tiếp trong dãy đều có tổng không vượt quá giá trị \(X\).

Input

  • Dòng đầu chứa hai số nguyên \(N\) và \(X\) (\(2\leq N\leq 10^5\), \(0\leq X\leq 10^9\)).

  • Dòng tiếp theo chứa \(N\) số nguyên \(a_1\), \(a_2\),..., \(a_N\) (\(0\leq a_i\leq 10^9\)).

Output

  • Một số nguyên là số thao tác ít nhất cần thực hiện.

Example

Test 1

Input 
3 3
2 2 2
Output 
1
Note

Ta cần thực hiện một thao tác duy nhất là giảm \(a_2\) một đơn vị.

Test 2

Input 
6 1
1 6 1 2 0 4
Output 
11

Test 3

Input 
5 9
3 1 4 1 5
Output 
0

Bình luận