우유 생산 증가에 관한 잡지 기사를 읽고 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