#H1000. 肥得更高

肥得更高

题目背景

众所周知,金坷垃已经逐渐退出历史舞台,但是仍有一部分人相信金坷垃才是最好的肥料!

因此,他们需要新的意识形态,来为他们所追求的肥料辩护; 他们需要新的理念、新的手段,来为金坷垃的生产提供支持。 这样,一种崭新的肥料精神就诞生了。 肥料复兴,是反对肥料粗制滥造,追求创新的新肥料文化的运动。 它必将成为推动金坷垃走得更远、飞得更高的重要力量。

题目描述

现在,你有n亩的小麦地需要增产,你拥有一些金坷垃,但是金坷垃极其稀少,掺肥料也只够你撒K次。

众所周知,金坷垃能激活土壤深处的氮磷钾,同一块地可以撒多次肥料,但是效果是有略微衰减的。

实地考察后你发现,第i亩土地第x次撒肥料增产a[i]-x+1公斤。

小H将代替你去撒肥料,但是他是个蒟蒻,完全不动大脑,所以你想知道如果他随机撒肥料,最坏情况下小麦将增产多少,最好情况下将增产多少?(他最多只会对第i亩地撒肥料a[i]次)

Format

输入格式

第一行两个整数n,K

第二行n个整数,第i个整数为a[i].

输出格式

输出最大值,最小值,空格隔开

输入输出样例

5 10
10 3 3 1 2
58 26

说明/提示

对于30%的数据n,k<=1000

对于70%的数据n,k<=200000

对于100%的数据n,k,a[i]<=1000000