Trong một thiên hà rộng lớn, có \(N\) hành tinh nằm thẳng hàng trong một khu vực. Mỗi hành tinh có một lượng tài nguyên nhất định. Một nhóm phi hành gia được giao nhiệm vụ đến thăm đúng \(K\) hành tinh để thu thập càng nhiều tài nguyên càng tốt.
Tuy nhiên, do hạn chế về năng lượng, họ chỉ được phép ghé thăm đúng \(K\) hành tinh trong số \(N\) hành tinh có sẵn. Mỗi hành tinh thứ \(i\) có một giá trị tài nguyên là \(a_i\), giá trị này có thể dương (tài nguyên quý giá) hoặc âm (chứa chất thải nguy hiểm).
Nhiệm vụ của bạn là giúp các phi hành gia chọn ra \(K\) hành tinh sao cho tổng tài nguyên thu được là lớn nhất.
Input
Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \leq K \leq N \leq 10^5\)) --- số hành tinh và số hành tinh mà nhóm phi hành gia có thể thăm.
Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(-10^5 \leq a_i \leq 10^5\)) --- lượng tài nguyên trên mỗi hành tinh.
Output
In ra một số nguyên duy nhất --- tổng lượng tài nguyên lớn nhất mà phi hành gia có thể thu được khi ghé thăm đúng \(K\) hành tinh.
Example
Test 1
Input
4 2
2 4 6 8Output
14Note
- Với test ví dụ đầu tiên, các phi hành gia sẽ lựa chọn thăm và thu thập tài nguyên từ hành tinh số \(3\) và hành tinh số \(4\).
- Với test ví dụ thứ hai, các phi hành gia sẽ lựa chọn thăm và thu thập tài nguyên từ hành tinh số \(1\), số \(2\), số \(3\) và số \(4\).
Test 2
Input
4 4
5 5 5 5Output
20Scoring
- \(10\%\) số test tương ứng với \(10\%\) số điểm có \(N = 1\).
- \(10\%\) số test tương ứng với \(10\%\) số điểm có \(N = 2\).
- \(20\%\) số test tương ứng với \(20\%\) số điểm có \(N \leq 20\).
- \(40\%\) số test tương ứng với \(40\%\) số điểm có \(N \leq 1000\).
- \(20\%\) số test tương ứng với \(20\%\) số điểm có \(N \leq 10^5\).
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.