Sau khi Bờm đáp ứng hết các điều kiện mà Phú Ông đưa ra, Bờm lại thắng cuộc một lần nữa. Vì phần thưởng lần này quá lớn nên Bờm vội chạy về và lục soát khắp nhà mới tìm được một cái ba lô chứa được trọng lượng không vượt quá S. Bờm vội vã mang đến nhà Phú Ông nhận thưởng. Phú Ông có N thỏi vàng có trọng lượng lần lượt là a₁, a₂, …, a_N để cho Bờm lựa chọn. Bờm rất cẩn thận lựa chọn các thỏi vàng cho vào ba lô sao cho tổng trọng lượng lớn nhất mà ba lô không bị rách (ba lô sẽ bị rách khi chứa trọng lượng lớn hơn S và khi đó Bờm phải đền gấp đôi số vàng lấy được).

Yêu cầu: Bạn hãy tính toán giúp Bờm có thể chọn những thỏi vàng để tổng trọng lượng lớn nhất và có bao nhiêu cách lựa chọn như vậy?

Dữ liệu

• Dòng 1 ghi số N và S (0 < N ≤ 1000; 0 < S ≤ 50000; N*S < 5x10⁶);
• Dòng 2 ghi số N số a[i] (0 < a[i] ≤ 1000);

Kết quả

• Nếu có phương án:
  • Dòng 1 ghi tổng trọng lượng lớn nhất có thể
  • Dòng 2 ghi số cách Bờm có thể lựa chọn để đạt tổng trọng lượng lớn nhất (hai cách chọn khác nhau nếu khác nhau ít nhất một thỏi vàng)
• Ngược lại nếu ba lô của Bờm quá tồi nên không đựng được bất cứ một thỏi vàng nào thì ghi duy nhất số 0