Vượt ải

Quân đang đi vượt ải Codeforces. Để trở thành master, Quân phải vượt qua \(n\) con quái vật. Con quái vật thứ \(i\) sẽ làm Quân hao tổn \(a_i\) công lực. Và vì các ải này diễn ra liên tiếp, Quân không có thời gian để hồi phục công lực. Quân 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 Quân có \(10\) công lực, và con quái vật đầu tiên có sức mạnh \(a_1 = 4\), Quân 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\), Quân sẽ bị đánh gục ở ải này.

Quân đã 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, Quân 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 Quân 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à Quân phải tính toán sử dụng sao cho tối ưu.

Quân 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 Quân 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 Quân cần chuẩn bị trước khi vượt ải.

Example

5 5
1 2 6 7 3

15

5 3
1 1 1 1 1

5

Scoring

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