Após ler um artigo sobre aumentar a produção de leite, Bessie estuda pressão atmosférica para agradar a Farmer John.

Faz $N$ medições ($(1 \le N \le 100)$), chamadas $M_{1}$ a $M_{N}$ ($(1 \le M_{i} \le 1,000,000)$), numeradas na ordem observada.

Para caracterizar a pressão do dia busca um subconjunto fiel que limite o erro abaixo: $K$ índices ($(1 \le K \le N)$) $s_{j}$ com $1 \le s_1 < s_2 < \cdots < s_K \le N$.

Cada medição antes da primeira escolhida, entre duas escolhidas consecutivas ou após a última gera erro. O erro total do conjunto $s_{j}$ é a soma dos erros individuais.

Para medições cujo índice $i$ não está em $s_{j}$:

• se $i$ é menor que $s_1$, o erro é:

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

• se $i$ está entre $s_j$ e $s_{j+1}$, o erro é:

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

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

• se $i$ é maior que $s_K$, o erro é:

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

Dado o erro máximo $E$ ($(1 \le E \le 1,000,000)$), determine o tamanho mínimo de um subconjunto com erro no máximo $E$.

Entrada

• Linha $1$: inteiros $N$ e $E$ separados por espaços.

• Linhas $2,\ldots,N+1$: a linha $i+1$ contém o inteiro $M_{i}$.

Saída

• Linha $1$: dois inteiros separados, tamanho mínimo para erro no máximo $E$ e menor erro possível nesse tamanho.

Exemplos

Entrada 1

4 20
10
3
20
40

Saída 1

2 17

Note

São $4$ medições, limite $20$, valores $10$, $3$, $20$, $40$ em ordem.

Escolher as medições $2$ e $4$ é ótimo, erro $17$. A primeira dá $2\times |10-3| = 14$ e a terceira $|2\times 20 - (3+40)| = 3$.

Autor do problema: Jeffrey Wang, 2007