Apple Merchant

Program time limit: 1 second

Program memory limit: 256 MB

Noah the studious guy is buying caterpillows(a special type of caterpillar that is soft like pillows) for his M ducklings.

There are N caterpillows to choose from, each with a different price $A_i$, but the data from his ship’s scanner is messy and unsorted.

Help Noah figure out which how much he have to spend to buy at least to buy M different caterpillows, so there is at least one for each of his ducklings.

If impossible, output -1.

Input

• The first line of inputs contains two integers, N and M.
• The following line contains N integers, with the ith integer being $A_i$.

You should read from standard input.

In Python, you could use the following code.

N, M = map(int, input().split())
A = list(map(int, input().split()))

In C or C++, you could use the following code.

const int LEN = 1e5+10;
int N, M;
scanf("%d%d", &N, &M);
int a[LEN];
for (int i = 0; i < N; i++) {
    scanf("%d", &a[i]);
}

Constraints

For all test cases:

• $0 \le N \le 10^5$.
• $0 \le M \le 10^5$.
• $1 \le A_i \le 10^9$.

Additionally:

• For Subtask $1$ ($50\%$ of points): $N,M \leq 1000$.
• For Subtask $2$ ($50\%$ of points): there are no additional constraints.

Output

one integer, the least amount of money.

You should write to standard output.

In Python, you could use the line print(answer).

In C or C++, you could use the line printf("%d\n", answer);.

Sample Input 1

5 2
6 7 4 1 2

Sample Output 1

3

Explanation 1

Answer is optimal if Noah buys the last two caterpillows.

Sample Input 2

5 6
6 7 4 1 2

Sample Output 2

-1

Explanation 2

There are not enough caterpillows! Noah will sadly fail to feed all his ducklings.

Scoring

For each subtasks (worth $50\%$, and $50\%$ of points, as per the Constraints section), your program will be run on multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves that subtask. Your program will receive the points for each subtask it solves. Recall that your final score on the task is the score of your highest scoring submission.

Submit

The contest ended at 8:16 p.m. AEST on Thursday 2nd July. All submissions will be unofficial .