Giải bài trực tuyến

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ể. 

Input

• Dòng đầu 3 số N, M, K. (1 ≤ N ≤ 1.000.000, 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.

Output

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

Example

Input:
5 1 2
1
1
1
1
1

Output:
7