Vượt Ải

Xem PDF

Điểm: 200 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

ami đang đi vượt ải Codeforces. Để trở thành master, ami phải vượt qua \(n\) con quái vật. Con quái vật thứ \(i\) sẽ làm ami hao tổn \(a_i\) công lực. Và vì các ải này diễn ra liên tiếp, ami không có thời gian để hồi phục công lực. ami sẽ gục ngã nếu sau một trận chiến, công lực còn lại bé hơn hoặc bằng \(0\).

Ví dụ: nếu ban đầu ami\(10\) công lực, và con quái vật đầu tiên có sức mạnh \(a_1 = 4\), ami sẽ vượt ải thành công và còn \(6\) công lực. Nếu con quái vật thứ hai có sức mạnh ít nhất là \(6\), ami sẽ bị đánh gục ở ải này.

ami đã nghiên cứu rất kỹ về đối thủ của mình. Anh biết rằng sức mạnh của chúng tương ứng là \(a_1, a_2, ..., a_n\). Và để thêm phần kỹ càng, ami sẽ mang theo một bộ giáp có thể chống được \(k\) sát thương. Nói cách khác, nếu ami sử dụng bộ giáp này khi đấu với quái vật thứ \(i\) thì chỉ mất đi \(max(0, a_i - k)\) công lực. Tuy nhiên, bộ giáp này chỉ sử dụng được cho \(1\) ải duy nhất và ami phải tính toán sử dụng sao cho tối ưu.

ami muốn vượt qua cả \(n\) ải này. Hỏi ban đầu anh phải chuẩn bị ít nhất bao nhiêu công lực? Biết rằng ami rất bá đạo nên sẽ sử dụng giáp một cách tối ưu.

Input

  • Dòng đầu tiên chứa hai số nguyên dương \(n, k \ (k \leq 10^9)\) tương ứng là số quái vật và sức mạnh của giáp.
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\) là sức mạnh của \(n\) con quái vật.

Output

  • In ra một số nguyên là công lực ít nhất ami cần chuẩn bị trước khi vượt ải.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(n \leq 1000\).
  • Subtask \(2\) (\(50\%\) số điểm): \(n \leq 10^5\).

Example

Test 1

Input
5 5
1 2 6 7 3
Output
15
Note

Trong test ví dụ 1, ami sẽ chuẩn bị \(15\) công lực và dùng giáp ở ải thứ 3. Qua ải 1, anh còn \(14\) công lực. Qua ải 2, anh còn \(12\) công lực. Nhờ sử dụng giáp ở ải 3, anh chỉ mất 1 công lực và còn \(11\) công lực. Quả ải 4 và 5, anh mất thêm \(7+3=10\) công lực. Cuối cùng, ami còn đúng \(1\) công lực, vừa đủ để sống sót.

Test 2

Input
5 3 
1 1 1 1 1
Output
5
Note

Trong test ví dụ 2, ami có thể dùng giáp ngay ải đầu tiên và sẽ không mất công lực nào ở ải đó. \(4\) ải còn lại tiêu hao \(4\) công lực nên ami vượt ải thành công.


Bình luận