Bò Ba-ri


Submit solution

Points: 0.58 (partial)
Time limit: 0.375s
Memory limit: 512M

Problem type

Học theo những gì đọc được từ một bài báo viết về việc tăng sản lượng sữa, Bessie đã biến mình trở thành một con bò Ba-ri bằng cách tìm hiểu về áp suất không khí để lấy lòng Farmer John.

Cô ta đã làm \(N\) phép đo (\(1 \le N \le 100\)) trong ngày. Để thuận tiện, chúng lần lượt được gọi là \(M_1\), \(M_2\), ..., \(M_N\) (\(M_i \le\) \(10^6\)). Các phép đo được đánh số theo thứ tự Bessie thực hiện chúng.

Để thể hiện được những phân tích về áp suất khí quyển trong ngày, Bessie đang để tâm đến việc tìm một tập hợp con của các phép đo, biểu thị bởi \(K\) (\(1 \le K \le N\)) chỉ số \(s_j\) (trong đó \(1 \le s_1 \le s_1 \le\) ...\(\le s_K \le N\)), thể hiện chính xác được toàn bộ các phép đo, tức là, giới hạn sai số trong khoảng cho phép.

Trong bất kì tập hợp các phép đo nào, một lỗi xuất hiện ở mỗi phép đo có vị trí:

  1. trước phép đo đầu tiên trong tập hợp;
  2. giữa hai phép đo liên tiếp trong tập hợp;
  3. sau phép đo cuối cùng trong tập hợp.

Tổng sai số của tập hợp đó được tính bằng tổng các lỗi trong các phép đo.

Cụ thể, với mỗi phép đó có chỉ số \(i\) mà không nằm trong tập hợp các phép đo đang xét:

  • Nếu \(i < s_1\), sai số được tính như sau: \(2 \times |M_i - M_{s_1}|\)
  • Nếu \(s_j < i < s_{j+1}\), sai số được tính như sau: \(|2 \times M_i - Sum(s_j, s_{j+1})|\) trong đó \(Sum(x\), \(y)\) = \(M_x + M_y\)
  • Nếu \(s_K < i\), sai số được tính như sau: \(2 \times |M_i - M_{s_K}|\)

Cho biết sai số tối đa là \(E\) (\(E \le 10^6\)), xác định số phần tử của tập hợp nhỏ nhất tạo ra sai số không vượt quá \(E\) và sai số của tập đó.

Input

  • Dòng \(1\): Chứa hai số nguyên cách nhau bởi khoảng trắng: \(N\) và \(E\)
  • Dòng \(2 \dots N+1\): Dòng \(i+1\) chứa số nguyên \(M_i\)

Output

  • Hai số nguyên cách nhau bởi khoảng trắng: số phần tử của tập hợp các phép đo nhỏ nhất tạo ra sai số không vượt quá \(E\) và sai số tập hợp đó tạo ra. Nếu nhiều tập có cùng số lượng phần tử thì chọn tập có sai số nhỏ nhất.

Sample Input

4 20
10
3
20
40

Sample Output

2 17

Note

Bessie tiến hành \(4\) phép đo; sai số tối đa cho phép là \(20\). Giá trị các phép đo lần lượt là: \(10\), \(3\), \(20\), \(40\)

Chọn phép đo thứ hai và thứ tự là giải pháp tốt nhất, cho sai số là \(17\). Sai số trong phép đo thứ nhất là \(2 \times|10-3|=14\); sai số trong phép đo thứ hai là \(|2 \times 20-(3+40)|=3\).


Comments

There are no comments at the moment.