Olympic Toán học Quốc tế (IMO) là một cuộc thi toán dành cho học sinh trung học phổ thông, được tổ chức hằng năm. Kỳ thi IMO năm 2025 diễn ra cùng thời điểm với EGOI. Khi bạn đang đọc những dòng này, cả hai ngày thi của IMO đều đã kết thúc và việc chấm thi có lẽ cũng đã gần hoàn tất. Khác với các cuộc thi lập trình như EGOI, việc chấm thi được thực hiện thủ công, một quá trình dài và vất vả.

Năm nay, IMO có ~M~ bài toán (được đánh số từ ~0~ đến ~M-1~), mỗi bài có điểm tối đa là ~K~. Có ~N~ thí sinh tham gia cuộc thi. Thí sinh thứ ~i~ nhận được điểm ~a_{i,j}~ ở bài ~j~, trong đó ~a_{i,j}~ là một số nguyên từ ~0~ đến ~K~, kể cả hai đầu mút. Thứ hạng của các thí sinh được xác định theo tổng điểm của mỗi thí sinh; nếu bằng điểm thì xét chỉ số của thí sinh. Cụ thể hơn, thí sinh ~x~ xếp hạng cao hơn thí sinh ~y~ nếu:

• tổng điểm của thí sinh ~x~ lớn hơn tổng điểm của thí sinh ~y~,

• hoặc tổng điểm của họ bằng nhau và ~x < y~.

Để công bố bảng xếp hạng cuối cùng, ban tổ chức cần công bố một số giá trị ~a_{i,j}~. Nếu một giá trị chưa được công bố, ta chỉ biết rằng đó là một số nguyên từ ~0~ đến ~K~, kể cả hai đầu mút.

Ban tổ chức muốn tiết lộ ít giá trị ~a_{i,j}~ nhất có thể. Đồng thời, họ cần bảo đảm rằng mọi người đều biết chính xác bảng xếp hạng cuối cùng. Nói cách khác, họ phải tiết lộ một tập hợp các giá trị sao cho bảng xếp hạng duy nhất phù hợp với tập hợp đó chính là bảng xếp hạng đúng.

Tìm ~S~ nhỏ nhất sao cho có thể tiết lộ ~S~ giá trị ~a_{i,j}~ theo cách xác định duy nhất toàn bộ thứ hạng của các thí sinh.

Input

Dòng đầu tiên chứa ba số nguyên ~N~, ~M~ và ~K~: lần lượt là số thí sinh, số bài toán và điểm tối đa của mỗi bài.

Tiếp theo là ~N~ dòng, trong đó dòng thứ ~i~ chứa các giá trị ~a_{i,j}~. Nghĩa là dòng đầu tiên trong số này chứa ~a_{0,0}, a_{0,1}, \dots, a_{0,M-1}~, dòng thứ hai chứa ~a_{1,0}, a_{1,1}, \dots, a_{1,M-1}~, và cứ như vậy.

Output

In ra một số nguyên ~S~, là số lượng điểm ít nhất có thể được tiết lộ để bảng xếp hạng cuối cùng được xác định duy nhất.

Scoring

• ~2 \le N \le 20000~.

• ~1 \le M \le 100~.

• ~1 \le K \le 100~.

• ~0 \le a_{i,j} \le K~ với mọi cặp ~i,j~ thỏa mãn ~0 \le i \le N-1~ và ~0 \le j \le M-1~.

Lời giải của bạn sẽ được kiểm tra trên một số nhóm test, mỗi nhóm có một số điểm nhất định. Mỗi nhóm test chứa một tập hợp các test. Để nhận được điểm của một nhóm test, bạn cần giải đúng tất cả các test trong nhóm đó.

Subtask	Điểm	Ràng buộc
1	~10~	~N=M=2~ và ~K=1~
2	~13~	~N=2~
3	~10~	~N \cdot M \le 16~
4	~18~	~K=1~
5	~21~	~N \le 10000~ và ~M,K \le 10~
6	~28~	Không có giới hạn gì thêm

Sample Input 1

4 6 7
7 7 0 2 7 0
7 3 0 7 2 1
7 0 0 7 0 0
7 7 7 7 7 1

Sample Output 1

20

Sample Input 2

2 1 1
1
0

Sample Output 2

1

Sample Input 3

2 2 7
7 4
7 0

Sample Output 3

2

Sample Input 4

2 2 1
0 1
1 0

Sample Output 4

2

Notes

Trong ví dụ thứ nhất, có thể tiết lộ ~20~ điểm như sau:

Thí sinh	Bài ~0~	Bài ~1~	Bài ~2~	Bài ~3~	Bài ~4~	Bài ~5~
~0~	~7~	~7~	~0~	~\bullet~	~7~	~\bullet~
~1~	~7~	~3~	~0~	~7~	~2~	~1~
~2~	~\bullet~	~0~	~0~	~\bullet~	~0~	~0~
~3~	~7~	~7~	~7~	~7~	~7~	~1~

Ở đây, ta biết tổng điểm của thí sinh thứ ba nằm trong khoảng từ ~0~ đến ~14~, chắc chắn thấp hơn tổng điểm của bất kỳ thí sinh nào khác. Có thể chứng minh rằng không thể tiết lộ ít hơn ~20~ điểm. Chẳng hạn, nếu ta giấu đi một trong các điểm không của thí sinh thứ ba thì tổng điểm của thí sinh này có thể lên đến ~21~. Điều này gây ra vấn đề vì thí sinh thứ hai có tổng điểm là ~20~, nhưng phải được bảo đảm xếp hạng cao hơn thí sinh thứ ba.

Ví dụ thứ nhất thỏa mãn ràng buộc của các nhóm test ~5~ và ~6~.

Trong ví dụ thứ hai, ta có thể chỉ tiết lộ điểm duy nhất của thí sinh thứ nhất, hoặc chỉ tiết lộ điểm duy nhất của thí sinh thứ hai (nhưng không tiết lộ cả hai). Nếu chỉ tiết lộ điểm của thí sinh thứ nhất, ta biết rằng thí sinh này có tổng điểm là ~1~. Điều này có nghĩa là ngay cả khi thí sinh thứ hai cũng có điểm là ~1~, thí sinh thứ nhất vẫn xếp hạng cao hơn vì có chỉ số nhỏ hơn. Tương tự, nếu chỉ tiết lộ điểm của thí sinh thứ hai, ta biết rằng thí sinh này có điểm bằng không, nghĩa là thí sinh thứ nhất sẽ xếp hạng cao hơn bất kể điểm của mình là bao nhiêu.

Ví dụ thứ hai thỏa mãn ràng buộc của các nhóm test ~2~, ~3~, ~4~, ~5~ và ~6~.

Ví dụ thứ ba thỏa mãn ràng buộc của các nhóm test ~2~, ~3~, ~5~ và ~6~.

Ví dụ thứ tư thỏa mãn ràng buộc của tất cả các nhóm test.

Ghi công và giấy phép

Bài toán này có nguồn gốc từ EGOI 2025 (Olympic Tin học nữ châu Âu), Ngày 2, được tổ chức tại Bonn, Đức.

• Đề bài gốc: IMO

• Tác giả: Eliška Macáková.

• Chủ sở hữu bản quyền: Olympic Tin học nữ châu Âu 2025.

• Tài liệu chính thức: Đề bài và lời giải · Dữ liệu kiểm thử, trình chấm và các bản dịch

• Giấy phép: Creative Commons Ghi công – Chia sẻ tương tự (CC BY-SA), theo siêu dữ liệu chính thức của bài toán. Siêu dữ liệu không chỉ rõ phiên bản giấy phép.

• Các thay đổi: Dịch sang tiếng Việt và định dạng lại cho ClueOJ.

Bản dịch này được phân phối theo cùng các điều khoản CC BY-SA áp dụng cho bài toán gốc.

ClueOJ không có quan hệ liên kết với EGOI hoặc ban tổ chức EGOI 2025, cũng không được các bên này chứng thực.