Question

Best Median With Cheapest Team

An Amazon hiring team is forming a final interview panel from n candidates.

The score of candidate i is a_i.

The team must choose exactly k candidates.

Among all possible choices of k candidates, the team first wants to maximize the median score. If there are multiple choices with the same maximum median score, the team wants the minimum possible total score among them.

Your task is to print the maximum possible median and the minimum possible total score among all choices that achieve this median.

The median of k chosen candidates is the element at position KaTeX can only parse string typed expression after sorting the chosen scores in non-decreasing order using 1-based indexing.

Input

The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of candidates and the number of candidates to choose.

The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the candidate scores.

Output

Print two integers — the maximum possible median and the minimum possible total score among all choices of KaTeX can only parse string typed expression candidates that achieve this median.

Example

Example 1:
Input

6 3

8 1 5 2 9 4

Output

8 18

Explanation
For KaTeX can only parse string typed expression, the median position is KaTeX can only parse string typed expression.
The maximum possible median is KaTeX can only parse string typed expression. To achieve this, one optimal choice is KaTeX can only parse string typed expression. After sorting, it becomes KaTeX can only parse string typed expression, whose median is KaTeX can only parse string typed expression. The total score is KaTeX can only parse string typed expression, which is minimum among all choices with median KaTeX can only parse string typed expression.

Example 2:
Input

5 4

7 2 9 1 8

Output

7 25

Explanation
For KaTeX can only parse string typed expression, the median position is KaTeX can only parse string typed expression.
The maximum possible median is KaTeX can only parse string typed expression. Choose KaTeX can only parse string typed expression. After sorting, the median is KaTeX can only parse string typed expression, so this choice is not valid for median KaTeX can only parse string typed expression.
A valid minimum-sum choice is KaTeX can only parse string typed expression. After sorting, it becomes KaTeX can only parse string typed expression, whose median is KaTeX can only parse string typed expression. The total score is KaTeX can only parse string typed expression.

Example 3:
Input

5 1

10 3 8 1 6

Output

10 10

Explanation
When KaTeX can only parse string typed expression, the median is the only chosen element. To maximize the median, choose KaTeX can only parse string typed expression. The minimum total score is also KaTeX can only parse string typed expression.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions