Ngày Lập Trình Viên

Để chào mừng Ngày Nhà giáo Việt Nam 20/11, trường làng Big-O tổ chức một kỳ thi lập trình dành cho tất cả học sinh trong trường. Ban tổ chức quyết định mở M nội dung thi đấu khác nhau. Sau khi kết thúc đợt đăng ký, ban tổ chức đã ghi nhận được N học sinh đăng ký dự thi.

Vì số lượng học sinh tham gia quá đông trong khi hệ thống phòng máy của trường chỉ có tổng cộng K máy tính, ban tổ chức quyết định chia các thí sinh thành các bảng đấu nhỏ. Ở mỗi vòng, các thí sinh còn lại của một nội dung được chia thành ít bảng nhất có thể, mỗi bảng có tối đa K thí sinh và thi đấu theo thể thức loại trực tiếp: người chiến thắng ở mỗi bảng sẽ giành quyền đi tiếp vào vòng trong, quá trình này lặp lại cho đến khi tìm ra người vô địch. Nếu một bảng đấu chỉ có 1 thí sinh, thí sinh đó sẽ được đặc cách vào thẳng vòng tiếp theo mà không cần thi đấu.

Nhà trường cần biết chính xác số lượng trận đấu tối thiểu cần tổ chức để hoàn thành tất cả các nội dung thi đấu nhằm lên kế hoạch thời gian cụ thể.

Đầu vào:

• Dòng đầu tiên chứa 3 số nguyên N, M, K ($1 \leq N, M \leq 10^6$, $2 \leq K \leq 10^6$) lần lượt là số lượng thí sinh đăng ký, số lượng nội dung thi đấu và số lượng máy tính có thể sử dụng. Các nội dung thi đấu được đánh số từ 1 đến M.
• Dòng thứ hai chứa N số nguyên, số nguyên thứ $i$ cho biết nội dung thi đấu mà học sinh thứ $i$ đã đăng ký.

Đầu ra:

• Một số nguyên duy nhất là số trận đấu tối thiểu cần tổ chức.

Giải thích:

• Nội dung thi 1 cần tổ chức 3 trận đấu: 4 thí sinh được chia vào 2 trận để chọn ra 2 người vào vòng tiếp theo, sau đó là 1 trận chung kết để tìm ra người chiến thắng.
• Nội dung thi 2 cần tổ chức 1 trận đấu để tìm ra người chiến thắng.

Ví dụ 1:

Đầu vào:

6 2 2
1 1 2 1 2 1

Đầu ra:

4