{"code":"vuotai","name":"Vượt Ải","description":"[user:ami] đang đi vượt ải Codeforces. Để trở thành master, [user:ami] phải vượt qua $n$ con quái vật. Con quái vật thứ $i$ sẽ làm [user:ami] hao tổn $a_i$ công lực. Và vì các ải này diễn ra liên tiếp, [user:ami] không có thời gian để hồi phục công lực. [user: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$.\r\n\r\nVí dụ: nếu ban đầu [user:ami] có $10$ công lực, và con quái vật đầu tiên có sức mạnh $a_1 = 4$, [user: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$, [user:ami] sẽ bị đánh gục ở ải này. \r\n\r\n[user: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, [user: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 [user: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à [user:ami] phải tính toán sử dụng sao cho tối ưu. \r\n\r\n[user: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 [user:ami] rất bá đạo nên sẽ sử dụng giáp một cách tối ưu.\r\n\r\n<h4>Input</h4>\r\n\r\n+ 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.\r\n+ 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.\r\n\r\n<h4>Output</h4>\r\n\r\n- In ra một số nguyên là công lực ít nhất [user:ami] cần chuẩn bị trước khi vượt ải.\r\n\r\n<h4>Scoring</h4>\r\n\r\n+ Subtask $1$ ($50\\%$ số điểm): $n \\leq 1000$.\r\n+ Subtask $2$ ($50\\%$ số điểm): $n \\leq 10^5$.\r\n\r\n<h4>Example</h4>\r\n\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        5 5\r\n        1 2 6 7 3\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        15\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n\r\n        Trong test ví dụ 1, [user: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, [user:ami] còn đúng $1$ công lực, vừa đủ để sống sót.\r\n\r\n!!! question \"Test 2\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        5 3 \r\n        1 1 1 1 1\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        5\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n\r\n        Trong test ví dụ 2, [user: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 [user:ami] vượt ải thành công.","points":200.0,"partial":true,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}