题目描述

为了研究农场的气候, Betsy 帮助 FJ 做了 $n$ 次气压测量并按顺序记录了结果 $m_i$（$1\leq i\leq n$）。Betsy 想找出一部分测量结果来总结整天的气压分布。她想用 $k$ 个数 $s_j$（$1\leq j\leq k$）来概括所有测量结果。她想限制如下的误差：对于任何测量结果子集,每一个非此子集中的结果都会产生误差。总误差是所有测量结果的误差之和。更明确地说，对于每一个和所有 $s_j$ 都不同的 $i$：

• 如果 $i < s_1$，误差是 $2\cdot \left| m_i - m_{s_1} \right|$。
• 如果 $s_j\leq i \leq s_{j+1}$，误差是 $\left| 2 \cdot m_i - m_{s_j} - m_{s_{j-1}} \right|$。
• 如果 $i > s_k$，误差是 $2 \cdot | m_i - m_{s_k} |$。

Besty 给了最大允许的误差 $e$，找出最小的一部分结果使得误差最多为 $e$。

输入格式

第一行：两个空格分隔的数: $n$ 和 $e$。

第 $2\sim n+1$ 行：第 $i+1$ 行包含一次测量记录：$m_i$。

输出格式

• 第一行：共两个数：最少能达到误差小于等于 $e$ 的测量数目和使用那个测量数目能达到的最小误差。

4 20
10
3
20
40

2 17

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 100$，$1 \leq m_i \leq 1\times 10^6$，$1 \leq k \leq n$，$1 \leq s_1 < s_2 < ... < s_k \leq n$，$1 \leq e \leq 1\times 10^{6}$。

提示

Bessie 做了 $4$ 次记录，分别为 $10$，$3$，$20$，$40$ .最大允许误差是 $20$，选择第二和第四次测量结果能达到最小误差 $17$。第一次结果的误差是$2\times\left|10-3\right| = 14$，第三次结果的误差是$\left|2\times20 - (3+40)\right|=3$。

题目来源

Usaco 2009 Jan Gold