Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ZABAVA - ZABAVA

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

Được gửi lên bởi:Alex & Friends
Ngày:2014-12-06
Thời gian chạy:0.5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:COCI

hide comments
2017-11-23 04:14:20
ez for AC
2017-11-23 04:08:55


Last edit: 2017-11-23 04:09:27
2017-11-23 04:08:46
ĐM thằng bên trên
2017-11-23 04:08:31
kjlasdf giljadsh
2017-11-23 04:03:17
bài này dùng convex hull trick cơ bản ez :v
2017-11-23 04:02:45
bài này ez
2016-03-22 16:25:50
88,89 C++ printf scanf nha mấy bác
2015-11-15 05:40:26
tle hay wa thế
2015-01-22 15:05:55 N�ng D�n John
há há !! Đúng rồi anh Ares.....thằng đầu tiên nhận phòng...tự sướng
2014-12-19 04:20:53 [♥KC]★★★★ - OACOVE
Cái này ms zui nè : phòng ko có ai nhưng ta vẫn đuổi :3 :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.