Từ tiếng Rumani “popeală” bắt nguồn từ một tiểu thuyết lịch sử Rumani, trong đó Hoàng thân Moldavia Alexandru Lăpușneanul dùng một biến thể của từ này để mô tả cuộc trả thù sắp tới nhằm vào những kẻ tiếm quyền. Gần đây, từ này được dùng trở lại trong cộng đồng lập trình Rumani để chỉ những tình huống mà ban ra đề khiến thí sinh gặp khó khăn theo cách bất thường và thường không cố ý, chẳng hạn giới hạn thời gian quá chặt, bộ kiểm thử sai, đề bài sai hoặc bàn phím bị lấy mất. Bài toán này nói về một tình huống như vậy.

Một cuộc thi có N thí sinh và một bài toán gồm T bộ kiểm thử. Ban ra đề muốn chia các bộ kiểm thử thành tối đa S nhóm. Mỗi bộ kiểm thử thuộc đúng một nhóm; mỗi nhóm không rỗng và gồm các bộ kiểm thử liên tiếp.

Nếu một thí sinh làm sai ít nhất một bộ kiểm thử trong một nhóm thì thí sinh đó nhận 0 điểm cho nhóm ấy. Nếu làm đúng tất cả bộ kiểm thử trong nhóm thì điểm nhận được bằng tổng điểm của các bộ kiểm thử trong nhóm.

Sau cuộc thi, ban ra đề biết mỗi thí sinh làm đúng những bộ kiểm thử nào. Họ muốn chọn cách chia nhóm sao cho tổng điểm mà tất cả thí sinh có thể đạt được là nhỏ nhất.

Cho mảng Points gồm T số nguyên, trong đó Points[i] là điểm của bộ kiểm thử thứ i, và ma trận Results kích thước N × T. Results[i][j] = 1 nếu thí sinh thứ i làm đúng bộ kiểm thử thứ j, ngược lại bằng 0.

Với mỗi K từ 1 đến S, hãy tìm tổng điểm nhỏ nhất có thể đạt được nếu chia các bộ kiểm thử thành đúng K nhóm.

Dữ liệu vào

• Dòng đầu gồm ba số nguyên N, T, S.
• Dòng thứ hai gồm T số nguyên dương là các phần tử của mảng Points.
• N dòng tiếp theo, mỗi dòng là một xâu nhị phân độ dài T mô tả một hàng của ma trận Results.

Dữ liệu ra

In ra S dòng. Dòng thứ K chứa số điểm nhỏ nhất có thể đạt được khi chia các bộ kiểm thử thành đúng K nhóm.

Ràng buộc

• 1 ≤ T ≤ 20000.
• 1 ≤ N ≤ 50.
• 1 ≤ S ≤ min(50, T).
• 1 ≤ Points[i] ≤ 10000.
• (Points[1] + Points[2] + ... + Points[T]) × N ≤ 2000000000.

Phân nhóm

• Nhóm 1: T ≤ 40, đạt 8 điểm.
• Nhóm 2: T ≤ 500, đạt thêm 9 điểm.
• Nhóm 3: T ≤ 4000, đạt thêm 9 điểm.
• Nhóm 4: Không có ràng buộc bổ sung, đạt 74 điểm còn lại.

Ví dụ

2 3 3
4 3 5
101
110

0
8
16

Nguồn

CEOI 2016, Ngày 2, Bài 2.

Lưu ý: Câu “Bất cứ mã nào bạn viết đều có thể được dùng để chống lại bạn” trong đề gốc được ghi chú là một câu đùa.