题目描述
小粉兔在 T 大学就读。在 1 月 54 日,T 大学开始了一学期一度的期末考试环节。
小粉兔本学期有 n 科考试,按照时间先后顺序依次被标号为 1,2,⋯,n。每一科考试都具有一个难度系数 ai。
如果准备这么多考试,小粉兔很可能会压力激增。因此,他想要仅准备并参与一部分考试,而将剩余的科目申请缓考。具体的,他可以选择准备前任意科考试(可以是 0 门,可以是 n 门),而剩余的科目不做准备。
但是,缓考的考试在下学期仍然需要参加,所以小粉兔会对他的决策做一个评估。他会使用「压力值」去完成这一评估过程。
具体的,我们设小粉兔选择参加前 k 科考试(0≤k≤n)。给定一个压力系数 c,此时他的压力值 t 的计算方式如下:
t=i=1maxkai+c×(n−k)其中 i=1maxkai 代表 a1,a2,⋯,ak 中的最大值。特别的,如果 k=0,则 i=1maxkai=0。
现在,小粉兔知道了考试的科数 n 和每门考试的难度系数 a1,a2,⋯,an,请你帮他计算出「压力值」最小时需要准备的考试科目数量。
输入格式
输入共两行。
第一行为两个整数 n,c,分别代表考试的科目数和压力系数。
第二行为 n 个整数 a1,a2,⋯,an,代表每门考试的难度系数。
输出格式
输出共一行两个整数,依次代表小粉兔「压力值」最小时需要准备的考试科目数量 k 和对应的最小「压力值」。如果有多个 k 对应的「压力值」相同且最小,请在相应位置输出其中最小的一个。
提示
数据规模与约定
对于 100% 的数据,保证 0≤n≤106,1≤ai≤109,1≤c≤109。
测试点编号 |
n |
ai |
1 |
=0 |
≤109 |
2 |
=1 |
3∼5 |
≤10 |
6 |
≤106 |
=1 |
7∼10 |
≤109 |