Après un article sur l'augmentation de la production laitière, Bessie étudie la pression atmosphérique pour plaire à Farmer John.

Elle prend $N$ mesures ($(1 \le N \le 100)$), nommées $M_{1}$ à $M_{N}$ ($(1 \le M_{i} \le 1,000,000)$), numérotées dans l'ordre d'observation.

Pour représenter la pression du jour, elle cherche un sous-ensemble fidèle limitant l'erreur ci-dessous : $K$ indices ($(1 \le K \le N)$) $s_{j}$ tels que $1 \le s_1 < s_2 < \cdots < s_K \le N$.

Chaque mesure avant la première sélectionnée, entre deux sélectionnées consécutives ou après la dernière crée une erreur. L'erreur totale du choix des $s_{j}$ est la somme des erreurs individuelles.

Pour une mesure d'indice $i$ absent des $s_{j}$ :

• si $i$ est inférieur à $s_1$, l'erreur vaut :

$$ 2 * | M_i - M_{s_1} | $$

• si $i$ est entre $s_j$ et $s_{j+1}$, l'erreur vaut :

$$ | 2 * M_i - \operatorname{Sum}(s_j, s_{j+1}) | $$

où $\operatorname{Sum}(x, y) = M_x + M_y$ ;

• si $i$ est supérieur à $s_K$, l'erreur vaut :

$$ 2 * | M_i - M_{s_K} | $$

Étant donnée l'erreur maximale $E$ ($(1 \le E \le 1,000,000)$), trouvez la taille minimale d'un sous-ensemble d'erreur au plus $E$.

Entrée

• Ligne $1$ : entiers $N$ et $E$ séparés par un espace.

• Lignes $2,\ldots,N+1$ : la ligne $i+1$ contient l'entier $M_{i}$.

Sortie

• Ligne $1$ : deux entiers séparés, taille minimale pour une erreur au plus $E$ et plus petite erreur possible à cette taille.

Exemples

Entrée 1

4 20
10
3
20
40

Sortie 1

2 17

Remarque

Il y a $4$ mesures, limite $20$, valeurs $10$, $3$, $20$, $40$ dans l'ordre.

Choisir les mesures $2$ et $4$ est optimal, erreur $17$. La première donne $2\times |10-3| = 14$, la troisième $|2\times 20 - (3+40)| = 3$.

Auteur du problème : Jeffrey Wang, 2007