#P328. 练55.3 收益最大

练55.3 收益最大

说明

农夫John 余下了mm批干草无法处理,他准备要开一个拍卖会去出售他的干草。现在有nn个顾客,每个顾客的报价是aia_i。现在John要确定一个单价,所有报价大于等于单价的顾客将会买到11批干草(mm批干草不用全卖完),总共获得的金钱作为收益。那么问题来了,如何设定单价,使得收益最大。

输入格式

第一行两个整数mm,nn,分别表示mm批干草和nn个顾客。第二行nn个整数,aia_i表示第ii个顾客的报价。
数据范围:1<nm10001 < n,m ≤10001<ai100001 < a_i ≤ 10000

输出格式

两个用空格分隔的整数,分别表示单价和总收益。如果有多个相等的最大收益,选取单价最小的那个。

样例

5 4
2 8 10 7
7 21