#1268. ZABAVA

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

N sinh viên mới chuẩn bị được nhập vào kí túc xá của trường. Khu kí túc của trường gồm M phòng, mỗi phòng lúc đầu đều không có ai ở. Mỗi ngày có một sinh viên mới sẽ được chuyển vào một trong M phòng này. Khi một người mới đến, buổi tối hôm đó, cả phòng sẽ tổ chức một bữa tiệc để mừng thành viên mới, và họ tạo ra những tiếng ồn, có độ “ồn ào” bằng tổng số người có trong phòng. Trưởng khu kí túc xá không thích điều này, và ông quyết định vào buổi sáng sớm của ngày ông sẽ đuổi hết sinh viên trong một phòng nào đó ra ngoài để tránh sự ồn ào gây ra phiền phức cho ông. Những sinh viên này khi đã bị đuổi thì sẽ ra ngoài kí túc ở và không bao giờ trở lại nữa. Tuy nhiên, trong N ngày, ông chỉ được phép làm việc này K lần. Hãy giúp ông đưa ra những quyết định đúng đắn, để tổng những tiếng “ồn” ông phải chịu là ít nhất có thể.

Dữ liệu vào:

  • Dòng đầu ghi ba số N, M, K\ (1≤N≤10^6,1≤M≤100,1≤K≤500) ;
  • N dòng sau, mỗi dòng là một số nguyên trong khoảng [1, M] chỉ phòng mà ngày thứ i sẽ có sinh viên mới vào.

Dữ liệu ra:

  • Số nguyên duy nhất là số lượng tiếng “ồn” nhỏ nhất có thể.

Ví dụ:

Dữ liệu vào:
5 1 2
1
1
1
1
1
Dữ liệu ra:
7

Giới hạn:

  • Subtask \#1: 40\%\text{ có }M=1 ;
  • Subtask \#2: 20\%\text{ có }N≤1000 ;
  • Subtask \#3: 20\%\text{ có }N≤50000 .