Được tin Sở Giáo dục và Đào tạo TP Đà Nẵng quyết định ngừng trợ cấp học bổng cho học sinh các lớp chuyên của trường Lê Quý Đôn để nâng mức tiền thưởng cho thí sinh đạt giải Học sinh giỏi quốc gia và Olympic quốc tế, Tuấn hết sức vui mừng vì giờ đây cậu đã có thêm một nguồn động lực mạnh mẽ để chăm chỉ ôn tập cho kỳ thi VOI 2019 sắp tới. Tuấn quyết định rủ toàn thể các học sinh trong đội tuyển của TP Đà Nẵng nghỉ một buổi học bồi dưỡng trên trường để cùng nhau ra gầm cầu Rồng nhảy Flashmob ăn mừng tin vui trên. Tuấn yêu cầu các bạn học sinh xếp thành một đội hình gồm m hàng ngang và n hàng dọc. Sau khi kiểm tra kỹ năng của từng người một, Tuấn rút ra kết luận rằng học sinh đứng ở giao điểm của hàng ngang thứ i và hàng dọc thứ j có kỹ năng nhảy là T(i,j).

Đến tiết mục nhảy cuối cùng, Tuấn muốn tạo ra một điểm nhấn theo quan niệm toán học của cậu. Tuấn vẽ ra một bảng ô vuông gồm m hàng và l cột rồi viết ngẫu nhiên một trọng số nguyên không âm P(i,j) vào ô giao điểm của hàng thứ i và cột thứ j. Tuấn dự định chọn ra l hàng dọc liên tiếp trong đội hình học sinh và yêu cầu tất cả các học sinh đứng trong l hàng dọc này cùng di chuyển vào bảng ô vuông mà Tuấn đã vẽ ra, mỗi người đứng trên một ô sao cho vị trí tương đối của mỗi học sinh trong hàng ngang và hàng dọc ở đội hình mới phải giống y hệt với vị trí của họ ở đội hình học sinh ban đầu. Theo quan niệm của Tuấn, độ hài lòng của mỗi ô vuông trong bảng được tính bằng tích kỹ năng nhảy của học sinh đứng trên ô vuông đó và trọng số của nó. Độ hài lòng của mỗi cách chọn được tính bằng tổng độ hài lòng của tất cả ô vuông trong bảng trong cách chọn đó. Dưới đây là minh họa cho trường hợp m=2, n=5 và l=2.

Tuấn sẽ cảm thấy hoàn toàn thỏa mãn với một cách chọn nếu như độ hài lòng của cách chọn đó lớn hơn số nguyên W. Cậu muốn biết có bao nhiêu cách chọn khiến cậu thỏa mãn nhưng số học sinh có vẻ quá lớn để cậu có thể tính toán được hết các phương án. Tuấn bèn nhờ đến Lương và Định nhưng cả hai vẫn còn đang mải mê chơi đùa với những con số đặc biệt nên lập tức từ chối giúp đỡ cậu. Bạn hãy giúp Tuấn tìm ra lời giải để cậu có được niềm vui trọn vẹn trong buổi nhảy flashmob này nhé!

Yêu cầu: Cho trước số nguyên W cùng thông tin chi tiết về kỹ năng nhảy của từng học sinh và trọng số của từng ô trong bảng ô vuông, hãy xác định số cách chọn l hàng dọc liên tiếp trong đội hình học sinh để sắp xếp họ đứng vào bảng ô vuông sao độ hài lòng của nó lớn hơn W.

Dữ liệu: 

- Dòng đầu tiên chứa các số nguyên dương n, l, m và W. (m≤10; l≤n; W≤10^9)
- m dòng tiếp theo chứa thông tin về kỹ năng nhảy của từng học sinh trong đội hình, số nguyên thứ i ở dòng thứ j biểu thị giá trị T(i,j). (0≤T(i,j)≤100)
- m dòng tiếp theo chứa thông tin về trọng số của các ô trong bảng ô vuông, số nguyên thứ i ở dòng thứ j biểu thị giá trị P(i,j). (0≤P(i,j)≤100)

Kết quả:

Ghi ra một số nguyên duy nhất là số cách chọn có độ hài lòng lớn hơn W.