Đi siêu thị mua quà

Siêu thị mini gần nhà Bơ có bán ~n~ mặt hàng và mỗi mặt hàng đều có số lượng rất nhiều (không hạn chế). Mỗi mặt hàng đều có đơn giá nhất định được gán nhãn đàng hoàng. Nhân dịp Bơ thi IOE đạt giải, chú Anh hào phóng cho Bơ mua ~k~ mặt hàng không phân biệt loại hàng cũng như thứ tự chọn các loại mặt hàng. Vốn thông minh ngoài giỏi Anh văn còn rất giỏi Toán nên trong đầu Bơ đã có phương án chọn. Nhưng chú Anh cũng thông minh nên đã biết được ý đồ của Bơ, cho nên đưa ra thêm một câu hỏi cho Bơ như sau: Có bao nhiêu cách khác nhau để mua ~k~ mặt hàng không phân biệt loại hàng cũng như thứ tự chọn loại mặt hàng. Nếu trả lời được thì cho phép chọn phương án mua của mình.

Input

Dòng thứ nhất chứa hai số nguyên dương ~n, k~ thỏa ~1 \le n \le 30; 0 \le k \le 30~.

Dòng thứ hai chứa các số ~p_i~ là đơn giá của các mặt hàng thỏa ~1\le p_i \le 10^9~.

Output

In ra số cách mua theo yêu cầu và tổng tiền phải trả cho hóa đơn của Bơ.

Samples

3 4
22000 13000 45000

15 180000

7 5
23 12 43 4 5 23 78

462 390