REAL ESTATE

Đề bài

Tỷ phú Vương Lượng là một nhà đầu tư tài ba, năm nay, ông dự định sẽ mua một mảng đất ở bãi đất trống mới được khai thác ở ngoại ô thành phố X. Bãi đất trống là một hình chữ nhật kích thước \(n \times m\) được chia thành lưới ô vuông đơn vị, các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống và các cột của bảng được đánh số từ \(1\) đến \(m\) từ trái qua phải. Ô đất nằm giao giữa hàng thứ \(i\) và cột thứ \(j\) có trị giá là \(a_{ij}\).

Sau khi tính toán kỹ lưỡng, Vương Lượng quyết định ông muốn mua một mảng đất là một hình chữ nhật kích thước \(p \times q\) nằm trong giao giữa \(p\) hàng liên tiếp của vườn với \(q\) cột liên tiếp của vườn. Khi mua một mảng đất như vậy, ô đất có giá trị bằng trung vị trong các ô của mảng đất được chọn làm chi phí để mua mảng đất. Theo tính toán thuật của Vương Lượng, cách mua tối ưu và đảm bảo lãi tiền sau này sẽ là mua một mảng đất có chi phí là \(k\).

Nhắc lại trung vị: sắp dãy giá trị của các ô theo thứ tự tăng dần thành \(v_1 \le v_2 \le \dots \le v_{pq}\), thì chi phí của mảng đất là \(v_{(pq+1)/2}\).

Là nhân viên của Vương Lượng, bạn hãy đếm xem có bao nhiêu mảng đất kích thước \(p \times q\) có chi phí đúng bằng \(k\) để ông có thể đầu tư thu lời.

Dữ liệu vào

• Dòng đầu chứa bốn số nguyên dương \(n, m, p, q\)
• Dòng thứ hai chứa số nguyên \(k\)
• \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) số nguyên dương \(a_{ij}\)

Dữ liệu ra

• Một số nguyên duy nhất — số lượng mảng đất \(p \times q\) có trung vị bằng \(k\).

Ràng buộc

• \(1 \le n, m \le 2000\)
• Giá trị \(a_{ij}\) và \(k\) lên đến \(10^9\)

Sample Input 1

4 4 3 3
1
1 1 2 2
1 1 2 2
1 1 2 2
1 1 2 2

Sample Output 1

2

Giải thích

Có hai mảng đất kích thước \(3\times 3\) có trung vị bằng \(1\):

• Mảng có góc trên–trái tại \((1,1)\) và góc dưới–phải tại \((3,3)\).
• Mảng có góc trên–trái tại \((2,1)\) và góc dưới–phải tại \((4,3)\).