[Usaco2009 Jan]气象牛Baric

为了研究农场的气候，Bessie 帮助农夫 John 进行了 $N$ 次气压测量，并按时间顺序记录为 $M_1,M_2,\ldots,M_N$。

Bessie 希望从中选出 $K$ 次测量，用下标 $s_1,s_2,\ldots,s_K$ 表示，其中

$$1\le s_1<s_2<\cdots<s_K\le N。$$

所有未被选中的测量结果都会产生误差。对于每个不属于所选下标集合的 $i$，其误差按以下规则计算：

• 若 $i<s_1$，误差为

  $$2\lvert M_i-M_{s_1}\rvert。$$

• 若 $s_j<i<s_{j+1}$，误差为

  $$\lvert 2M_i-(M_{s_j}+M_{s_{j+1}})\rvert。$$

• 若 $i>s_K$，误差为

  $$2\lvert M_i-M_{s_K}\rvert。$$

总误差为所有未被选中的测量结果所产生误差之和。

给定最大允许误差 $E$，请找出使总误差不超过 $E$ 时所需的最少测量次数 $K$，并求出在使用 $K$ 次测量时能够达到的最小总误差。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $E$。

接下来 $N$ 行，第 $i$ 行包含一个整数 $M_i$，表示第 $i$ 次气压测量的结果。

输出格式

输出一行两个以空格分隔的整数，分别表示总误差不超过 $E$ 时所需的最少测量次数，以及使用该测量次数能够达到的最小总误差。

样例输入

4 20
10
3
20
40

样例输出

2 17

样例解释

Bessie 共进行了 $4$ 次测量，结果依次为 $10$、$3$、$20$ 和 $40$，最大允许误差为 $20$。

选择第 $2$ 次和第 $4$ 次测量时，可以达到最小总误差 $17$。其中，第 $1$ 次测量产生的误差为

$$2\lvert 10-3\rvert=14，$$

第 $3$ 次测量产生的误差为

$$\lvert 2\times20-(3+40)\rvert=3。$$

因此总误差为 $14+3=17$。

数据范围

• $1\le N\le 100$；
• $1\le M_i\le 10^6$；
• $1\le E\le 10^6$；
• $1\le K\le N$。

来源与许可

本题为 USACO 2009 January 试题「气象牛 Baric」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 20
10
3
20
40

输出

2 17