Đóng gói sản phẩm – Nghệ An 2025-2026

Đề bài

Công ty của gia đình Alice có $n$ sản phẩm với khối lượng lần lượt là $a_1, a_2, \dots, a_n$ . Công ty sẽ đóng gói thành các kiện hàng để gửi cho khách. Mỗi kiện hàng có đúng $k$ sản phẩm và khối lượng của các kiện hàng đều bằng nhau. Khối lượng của một kiện hàng bằng tổng khối lượng của $k$ sản phẩm trong kiện hàng đó. Chú ý là, một sản phẩm thuộc nhiều nhất một kiện hàng.

Alice muốn biết Công ty của gia đình mình có thể đóng gói được nhiều nhất bao nhiêu kiện hàng.

Dữ liệu vàoSANPHAM.INP

Dữ liệu cho từ tệp văn bản SANPHAM.INP gồm:

Dòng đầu tiên ghi hai số nguyên dương $n, k$ $(1 \le k \le 3; 1 \le n \le 10^5)$ .
Dòng thứ hai ghi $n$ số nguyên $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 1000)$ .

Kết quả raSANPHAM.OUT

Kết quả ghi ra tệp văn bản SANPHAM.OUT gồm một số nguyên là số lượng kiện hàng nhiều nhất có thể đóng gói được.

Ràng buộc

Có 40% số test ứng với $k = 1, n \le 1000$ ;
Có 40% số test ứng với $k = 2$ ;
Có 20% số test ứng với $k = 3, 1 \le a_i \le 3$ .

Ví dụ

Ví dụ 1

Dữ liệu vàoSANPHAM.INP

5 1
1 6 6 4 6

Kết quả raSANPHAM.OUT

Giải thích

Đóng gói được nhiều nhất 3 kiện hàng, mỗi kiện hàng gồm 1 sản phẩm.
Đó là các sản phẩm thứ 2, 3, 5.
Các sản phẩm này đều có khối lượng bằng 6.

Ví dụ 2

Dữ liệu vàoSANPHAM.INP

5 2
1 6 6 4 6

Kết quả raSANPHAM.OUT

Giải thích

Đóng gói được nhiều nhất một kiện hàng gồm 2 sản phẩm.
Có thể lấy hai sản phẩm bất kì để đóng gói thành 1 kiện hàng.

Ví dụ 3

Dữ liệu vàoSANPHAM.INP

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

Kết quả raSANPHAM.OUT

Giải thích

Đóng gói được nhiều nhất 3 kiện hàng, mỗi kiện hàng gồm 3 sản phẩm.
Cụ thể, 3 kiện hàng, mỗi kiện hàng gồm 3 sản phẩm có khối lượng như sau:
$\{1, 2, 2\}$ → tổng khối lượng bằng 5.
$\{1, 2, 2\}$ → tổng khối lượng bằng 5.
$\{1, 1, 3\}$ → tổng khối lượng bằng 5.