Vạn sự khởi đầu nan
Người xưa có câu "Vạn sự khởi đầu nan", chắc hẳn bạn cũng đã nghe câu này rất nhiều lần rồi. Nó có thể hiểu đơn giản là việc gì khi mới làm thì đều khó khăn, gặp nhiều gian nan, thử thách. Nhưng chớ nghĩ rằng việc khó ngay từ đầu thì mình bỏ qua, mà hãy luôn nhớ rằng thành công chỉ đến với người có ý chí. Phải có sự kiên trì, quyết tâm vượt qua các chông gai thì mới có thể mở khóa cánh cửa dẫn đến thành công được. Và ở môn học này cũng vậy, khi mới khởi đầu, bạn sẽ thấy nó thực sự khó nhằn vì những tư duy mới lạ, có thể sẽ chưa từng gặp trong các môn khác, có những thứ xa lạ như ra lệnh cho máy tính, thuật toán hay cấu trúc dữ liệu, ... Mọi thứ đều rất mới mẻ, nhưng nếu ta có thể quyết tâm, có đam mê theo đuổi, học vững chắc phần nền móng, thì dần dần sẽ có thể chinh phục được thêm nhiều những đỉnh cao khác mà thôi. Ngoài ra, đừng để những lời nói xung quanh làm nản đi ý chí của bạn!
Quay lại bài toán thì hiện tại Kudo đang chuẩn bị theo học ngành diễn xuất, và cậu cần phải học một số bài cơ bản ban đầu. Do tính chất của những bài này khá đơn giản và không liên quan đến với nhau lắm nên cậu hoàn toàn có thể chọn nên học bài nào trước. Nhưng vấn đề lại không chỉ có như vậy, do số liệu quá lớn nên cậu lại chẳng thể biết nên chọn để học những môn nào trước. Do rất quyết tâm theo đuổi đam mê nên độ yêu thích môn học của cậu ban đầu đang là Q. Nhưng có một số bài học lại có thể "giúp" độ yêu thích này bị giảm đi, và cũng có một số bài có thể làm tăng độ yêu thích. Sau khi học bài học có độ "ảnh hưởng sự yêu thích" là A, thì độ yêu thích của Kudo với môn học sẽ thay đổi từ K sang K+A. Và để Kudo có thể chinh phục được môn học, Chennqs -- một người bạn thân của cậu đã nhận lời giúp cậu sắp xếp bài học để cậu có thể học một cách hợp lý để luôn giữ cho Kudo một khí thế hừng hực khi học. Nhưng sau khi để ý thì cậu nhận thấy nhiều khi thì sắp xếp kiểu nào cũng làm cho độ yêu thích có giá trị âm tại một thời điểm nào đó. Sau một thời gian suy nghĩ thì cậu quyết định sẽ loại bỏ đi các bài đó và đánh dấu lại để Kudo có thể tìm thêm một số bài có độ "ảnh hưởng sự yêu thích" cao để có thể học hết những bài đó. Sau khi chọn xong, Chennqs sẽ cho Kudo biết được lượng bài học lớn nhất mà cậu có thể học và độ yêu thích lớn nhất của cậu sau khi học xong các bài đó! Nhưng do hiện tại Chennqs đang bận với dự án phim mới của mình nên đành nhờ lại các bạn. Hãy giúp Kudo và Chennqs biết được số bài học lớn nhất mà Kudo có thể học và độ yêu thích lớn nhất của cậu sau khi học xong các bài đó.
Giải thích: Do có nhiều cách chọn và sắp xếp bài học mà số bài học là bằng nhau nên chỉ lấy phương án có độ yêu thích lớn nhất sau khi học.
Cho số nguyên $N$ là số bài học tất cả và số nguyên $Q$ là độ yêu thích ban đầu của Kudo, ngoài ra có thêm $N$ số nguyên $A_i$ là độ "ảnh hưởng sự yêu thích" của bài học thứ $i$.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương $N,Q$ $(1\le N \le 10^5;0\le Q \le 10^9)$;
- Dòng tiếp theo chứa $N$ số nguyên $A_i$ $(|A_i| \le 10^9)$.
Kết quả
- Kết quả bài toán.
Ví dụ
Ví dụ 1
input
5 6
1 6 -7 -9 2
output
4
8
Giải thích
- Chennqs sẽ bỏ môn thứ 4 và cho Kudo học theo thứ tự: 1, 5, 2, 3 là 6 + 1 + 2 + 6 -- 7 = 8.
Comments