C. Maximum profit
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Rafa and Jan are like joints, how good they are but how bad they are.

There is a bank with a stack of $$$n$$$ checks, each having a specific face value in dollars.

The bank has a unique policy: they allow their customers to redeem a limited number of checks per day.

Your task is to help the bank's customers determine the maximum total value they can redeem in a single day.

Input

The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 10^{4})$$$ and $$$k$$$ $$$(1 \leq k \leq n)$$$, representing the number of checks and the maximum number of checks the bank allows to be redeemed in a day, respectively.

The second line contains $$$n$$$ integers $$$c_{1}, c_{2}, ..., c_{n}$$$ $$$(1 \leq c_{i} \leq 10^4)$$$, representing the face values of the $$$n$$$ checks.

Output

Output a single integer, the maximum total value that can be redeemed in a single day by choosing the optimal combination of $$$k$$$ checks.

Example
Input
3 2
11 5 10
Output
21
Note

The optimal strategy is to take the first and the third checks to get a sum of $$$21$$$ dollars.

—

Problem idea: danx

Problem preparation: danx

Ocurrences: Novice 3