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 có \(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

5 5
1 2 6 7 3

15

5 3 
1 1 1 1 1

5