Có \(k\) người bạn muốn vào một lớp học là ma trận \(n\times m\). Mỗi ghế hoặc trống (giá trị \(0\)), hoặc đã có học sinh với chiều cao bằng giá trị tại ô. Nhóm chọn một hàng \(i\) và \(k\) ghế trống liên tiếp từ cột \(j\) đến \(j+k-1\); họ được ngồi theo bất kỳ thứ tự nào. Một người chỉ ngồi được tại ghế khi mọi học sinh ở phía trước, tức cùng cột và có chỉ số hàng nhỏ hơn, đều thấp hơn nghiêm ngặt người đó. Hãy đếm số tập \(k\) ghế liên tiếp mà nhóm có thể sắp xếp để tất cả đều nhìn rõ.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n,m\le2000\), \(1\le k\le m\)). Dòng hai chứa chiều cao \(h_1,h_2,\ldots,h_k\) của các bạn. \(n\) dòng sau, mỗi dòng chứa \(m\) số nguyên \(a_{i,j}\); \(a_{i,j}=0\) nếu ghế trống, còn \(a_{i,j}\ge1\) là chiều cao của học sinh đang ngồi.

Dữ liệu ra

In số tập ghế liên tiếp phù hợp.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(11\) điểm: \(k\le2\).
2. \(13\) điểm: \(n,m\le200\).
3. \(29\) điểm: \(n,m\le500\).
4. \(57\) điểm: không có ràng buộc thêm.

Ví dụ

3 4 2
2 6
0 0 3 1
8 0 0 0
0 0 1 0

3

2 4 4
5 2 4 3
1 2 3 4
0 0 0 0

1

5 5 3
17 3 17
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

15

Nguồn

COCI 2025/2026 - Vòng 6, bài Učionica.

Đề bài và dữ liệu kiểm thử được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.