Chợ Trao Đổi

Ở một "Chợ Trao Đổi", bạn có thể mang một số món đồ của mình đến để đổi lấy các món đồ khác mà không mất phí.

Chợ có tất cả $n$ món đồ, mỗi món là duy nhất (chỉ có một bản). Món thứ $i$ có giá trị $c_i$. Bạn có thể mang một tập món đồ bất kỳ đến và đổi nó lấy một tập món đồ khác, với điều kiện hai tập không có món chung nào (vì mỗi món chỉ tồn tại một bản). Nói cách khác, tập $x$ có thể đổi thành tập $y$ bất kỳ miễn là không tồn tại món $p$ vừa thuộc $x$ vừa thuộc $y$.

Quy tắc công bằng của chợ: bạn không được đổi tập $x$ lấy tập $y$ nếu $s(x)+d<s(y)$, trong đó $s(·)$ là tổng giá trị các món trong tập. Tức là tổng giá trị của tập nhận về không được vượt quá tổng giá trị tập đem đổi cộng thêm $d$.

Mỗi ngày bạn chỉ được thực hiện một lần đổi. Ban đầu bạn không có món đồ nào (xem như đang sở hữu tập rỗng có giá trị $0$).

Bạn muốn cuối cùng sở hữu một tập món đồ có tổng giá trị lớn nhất có thể. Hãy tìm tổng giá trị đó và số ngày ít nhất để đạt được nó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $d$.
• Dòng thứ hai chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$ — giá trị của các món đồ.

Dữ liệu ra

In ra hai số nguyên cách nhau bởi dấu cách: tổng giá trị lớn nhất mà bạn có thể sở hữu, và số ngày ít nhất để đạt được tổng giá trị đó.

Ràng buộc

• $1\le n\le 50$
• $1\le d\le {10}^4$
• $1\le c_i\le {10}^4$

Ví dụ