Description

Because of the cows’ dieting campaign, FJ has a large amount of leftover hay he cannot use, so he plans to hold an auction to sell it.

He has $n$ batches of hay. He has $m$ customers, all of whom are farmers like him. Farmer $i$ says he will pay $p_i$ for each batch of FJ’s hay. Every farmer wants to buy exactly one batch (and only one).

To make sure the farmers do not envy each other, FJ decides to sell at a single fixed price. Every farmer whose bid is greater than or equal to FJ’s asking price will buy a batch.

Please help FJ find the lowest per-batch price that earns him the maximum total revenue.

Input Format

• The first line contains two integers $n$ and $m$ separated by a space.
• Lines $2$ through $m+1$: line $i+1$ contains a single integer $p_i$.

Output Format

Output one line with two space-separated integers: the lowest per-batch price FJ should set, and the maximum total revenue he can earn.

5 4
2
8
10
7

7 21

Hint

Sample Explanation
FJ has $5$ batches of hay, and $4$ farmers want to buy. Their bids per batch are $2$, $8$, $10$, and $7$.
FJ should set the price to $7$. Then $3$ farmers will buy, and FJ will earn $21$.

Constraints
For $100\%$ of the testdata, $1 \leq m, n \leq 1000$, $1 \leq p_i \leq 1,000,000$.

Translated by ChatGPT 5