Bài 4 : Khu vườn thượng uyển (5.0 điểm)

Vua của vương quốc Algorithmia muốn quy hoạch một khu vườn hình chữ nhật trong khuôn viên hoàng cung. Khu đất dự kiến được chia thành lưới ô vuông kích thước \(n \times m\). Mỗi ô \((i, j)\) có độ phì nhiêu của đất là \(a_{i,j}\).

Nhà vua muốn rào một khu đất hình chữ nhật con (có các cạnh song song với các cạnh của khu đất lớn) để trồng một loài hoa quý. Loài hoa này rất kén chọn, nó chỉ phát triển tốt nếu tổng độ phì nhiêu của toàn bộ khu đất hình chữ nhật đó nằm trong khoảng từ \(L\) đến \(R\).

Nhiệm vụ của bạn là đếm xem có bao nhiêu cách chọn một hình chữ nhật con thỏa mãn yêu cầu của nhà vua.

Input

Vào từ tệp văn bản KHUVUON.INP có cấu trúc:

• Dòng đầu tiên chứa bốn số nguyên \(n, m, L, R\) (\(1 \le n, m \le 500, 1 \le L \le R \le 10^{12}\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) số nguyên dương biểu diễn ma trận độ phì nhiêu \(a\) (\(1 \le a_{i,j} \le 10^9\)).

Output

Ghi ra tệp văn bản KHUVUON.OUT một số nguyên duy nhất là số lượng hình chữ nhật con thỏa mãn.

Example

3 3 3 5
1 1 1
1 1 1
1 1 1

10

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n, m \le 10\).
• Subtask 2 (\(30\%\) số điểm): \(n, m \le 100\).
• Subtask 3 (\(40\%\) số điểm): Không có ràng buộc gì thêm.