📖 Bài giảng & lời giải: đây là Bài tập 4 trong bài giảng Chuyên đề nhập môn 9: Cộng dồn 2 chiều trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Khu vườn là bảng gồm $n$ hàng, $m$ cột ô đất, ban đầu mọi ô đều khô (lượng nước bằng 0). Có $q$ lần tưới, lần tưới thứ $t$ đổ thêm $v_t$ lít nước vào mỗi ô của hình chữ nhật từ hàng $x_1$ tới hàng $x_2$, từ cột $y_1$ tới cột $y_2$. Cây chỉ sống được ở ô nhận được ít nhất $K$ lít nước sau tất cả các lần tưới. Hỏi có bao nhiêu ô cây sống được?

Dữ liệu vào

• Dòng 1: bốn số nguyên $n, m, q, K$ ($1 \le n, m \le 1000$, $1 \le q \le 10^5$, $1 \le K \le 10^{18}$).
• $q$ dòng tiếp theo, mỗi dòng gồm 5 số nguyên $x_1, y_1, x_2, y_2, v$ ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le m$, $1 \le v \le 10^9$) mô tả một lần tưới.

Kết quả

In ra một số nguyên là số ô có lượng nước không nhỏ hơn $K$.

Sample Input

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

Sample Output

5