Câu 3. (5.0 điểm) Đóng gói sản phẩm

Một công ty sản xuất có \(n\) sản phẩm với khối lượng lần lượt là \(a_1, a_2, \ldots, a_n\). Công ty sẽ đóng sản phẩm vào các kiện hàng. Mỗi kiện hàng có đúng \(k\) sản phẩm và khối lượng của kiện hàng là tổng khối lượng của \(k\) sản phẩm trong kiện đó.

Công ty muốn biết số lượng kiện hàng nhiều nhất có thể đóng được nếu mỗi kiện phải gồm đúng \(k\) sản phẩm và tổng khối lượng của mỗi kiện hàng không vượt quá \(m\).

Input

Dữ liệu: Gồm từ tệp SANPHAM.INP:

• Dòng đầu ghi ba số nguyên \(n, k, m\) (\(1 \le k \le 3; 1 \le n \le 10^5; 1 \le m \le 10^9\)).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 1000\)).

Output

Kết quả: Ghi ra tệp SANPHAM.OUT một số nguyên là số lượng kiện hàng nhiều nhất có thể tạo được.

Example

5 2 3
1 2 2 1 2

2

10 3 6
1 2 3 3 2 3 2 3 3 2

2

Scoring

Giới hạn:

• 40% số test ứng với \(k = 1, n \le 1000\).
• 40% số test ứng với \(k = 2\).
• 20% số test còn lại với \(k = 3, 1 \le a_i \le 3\).