VMMARBLE - Phân loại bi

Giới hạn
  • Thời gian: 3.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Bắn bi là một trò chơi yêu thích của Raldono và Balitello và hai người bạn của chủng ta vừa mua được N hộp bi gồm các viên bi với M màu khác nhau. Ban đầu, mỗi hộp có thể chứa các viên bi với nhiều màu khác nhau; hộp thứ i sẽ chứa A i, j viên bi màu j. Hai người bạn của chúng ta muốn phân loại các viên bi sao cho không có 2 viên bi khác màu nào nằm trong cùng 1 hộp. Các viên bi sẽ được chuyển giữa các hộp. Để đảm bảo các viên bi không bị hư hại, mỗi lần chỉ chuyển tối đa K viên bi từ 1 hộp sang 1 hộp khác.

Cả hai dự định sẽ cùng nhau phân loại bi. Tuy nhiên, với bản tính lười biếng của mình, Raldono bảo với Balitello rằng nếu cậu ta có thể tìm ra cách phân loại bi với ít lần chuyển bi nhất thì Balitello sẽ là người phải thực hiện công việc phân loại, ngược lại Raldono sẽ phải làm. Hãy giúp Raldono tìm số lần chuyển bi ít nhất để phân loại bi.

Input

  • Dòng 1 chứa 3 số nguyên N , M và K
  • N dòng tiếp theo, dòng thứ i chứa M số nguyên A i, 1 , A i,2 , ..., A i,M

Output

  • Một số nguyên là số lần chuyển bi ít nhất

Giới hạn

  • 0 ≤ A i, j ≤ 10 5
  • Subtask 1 (30%): 1 ≤ N ≤ 1000, 1 ≤ M ≤ 10, K = 1
  • Subtask 2 (70%): 1 ≤ N ≤ 50, 1 ≤ M ≤ 3, K = 2
  • M ≤ N

Example

Input:

3 2 1

5 3

4 6

1 9

Output:

8

Giải thích

Chuyển 3 viên bi màu 2 từ hộp 1 sang hộp 3.

Chuyển 4 viên bi màu 1 từ hộp 2 sang hộp 1.

Chuyển 1 viên bi màu 1 từ hộp 3 sang hộp 1.

  • Người up: voj
  • Nguồn bài: VNOI Marathon 2014 - flashmt