Vượt Ải

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
cuom1999
Dạng bài
Đ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 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

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


  • -46
    n3nhannxt    8:52 a.m. 13 Tháng 8, 2020

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • 0
      todonghai2k7    9:36 a.m. 13 Tháng 8, 2020

      1 downvote vì ko có giải thích :)))


      • 0
        tuanlinh    9:25 a.m. 13 Tháng 8, 2020

        có hướng dẫn rồi viết làm gì


        • 0
          vinhntndu    9:16 a.m. 13 Tháng 8, 2020

          1 downvote vì trình bày quá xấu, code lại dài


          • -7
            n3nhannxt    9:23 a.m. 13 Tháng 8, 2020

            Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


            • -2
              vinhntndu    9:35 a.m. 13 Tháng 8, 2020

              ok +0.5 upvode vì lần đầu, giữ -0.5 downvote vì code hơi xấu :>


              • -5
                TCA_Khoa    9:29 a.m. 13 Tháng 8, 2020

                Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


                • -5
                  n3nhannxt    9:44 a.m. 13 Tháng 8, 2020

                  Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

            5 bình luận nữa