Прочитав статью об увеличении надоев, Bessie стала изучать атмосферное давление, чтобы угодить Farmer John.

За день она делает $N$ измерений ($(1 \le N \le 100)$), названных $M_{1}$ — $M_{N}$ ($(1 \le M_{i} \le 1,000,000)$), пронумерованных в порядке наблюдения.

Для описания давления за день она ищет подмножество, точно отражающее все измерения и ограничивающее ошибку ниже: $K$ индексов ($(1 \le K \le N)$) $s_{j}$ с $1 \le s_1 < s_2 < \cdots < s_K \le N$.

Ошибка возникает для каждого измерения перед первым выбранным, между двумя последовательными выбранными и после последнего выбранного. Общая ошибка для набора $s_{j}$ — сумма отдельных ошибок.

Для измерений с индексом $i$, не входящим в $s_{j}$:

• если $i$ меньше $s_1$, ошибка равна:

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

• если $i$ между $s_j$ и $s_{j+1}$, ошибка равна:

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

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

• если $i$ больше $s_K$, ошибка равна:

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

Для максимальной ошибки $E$ ($(1 \le E \le 1,000,000)$) найдите размер наименьшего подмножества с ошибкой не более $E$.

Входные данные

• Строка $1$: целые $N$ и $E$ через пробел.

• Строки $2,\ldots,N+1$: строка $i+1$ содержит целое $M_{i}$.

Выходные данные

• Строка $1$: два целых через пробел — минимальный размер подмножества с ошибкой не более $E$ и минимальная ошибка среди подмножеств этого размера.

Примеры

Входные данные 1

4 20
10
3
20
40

Выходные данные 1

2 17

Примечание

Измерений $4$, предел ошибки $20$, значения по порядку $10$, $3$, $20$, $40$.

Лучше выбрать измерения $2$ и $4$, ошибка $17$. Ошибка первого — $2\times |10-3| = 14$, третьего — $|2\times 20 - (3+40)| = 3$.

Автор задачи: Jeffrey Wang, 2007