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

VMMARBLE - Phân loại bi

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 Ai, 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, MK
  • N dòng tiếp theo, dòng thứ i chứa M số nguyên Ai, 1, Ai,2, ..., Ai,M

Output

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

Giới hạn

  • 0 ≤ Ai, j ≤ 105
  • 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.


Được gửi lên bởi:VOJ Team
Ngày:2014-08-13
Thời gian chạy:3s
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:VNOI Marathon 2014 - flashmt

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.