Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ 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 bấm vào xem bà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

Cho một bảng ô vuông gồm ~n~ dòng và ~m~ cột. Các dòng được đánh số từ ~1~ đến ~n~, các cột được đánh số từ ~1~ đến ~m~. Ô nằm ở dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Có ~k~ ô màu đen trên bảng, ô đen thứ ~i~ nằm ở vị trí ~(x_i, y_i)~. Các ô còn lại trong bảng đều có màu trắng.

Bạn có thể thực hiện một trong hai loại thao tác sau (mỗi thao tác có thể được thực hiện nhiều lần hoặc không lần nào):

• Chọn một dòng chỉ gồm các ô màu trắng, và xóa dòng đó khỏi bảng.
• Chọn một cột chỉ gồm các ô màu trắng, và xóa cột đó khỏi bảng.

Hãy tìm cách thực hiện các loại thao tác trên, sao cho số ô còn lại trong bảng là nhỏ nhất có thể.

Dữ liệu vào

• Dòng đầu tiên gồm ba số nguyên ~n, m, k~ ~(1 \le n, m, k \le 10^5)~ – số dòng, số cột của bảng và số ô đen.
• ~k~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~x_i, y_i~ ~(1 \le x_i \le n,\ 1 \le y_i \le m)~ – vị trí của ô đen thứ ~i~. Dữ liệu vào đảm bảo không có hai ô đen nào ở cùng vị trí.

Kết quả

• In ra số ô còn lại nhỏ nhất có thể sau khi thực hiện hai loại thao tác trên.

Giới hạn

• Thời gian: 1 giây. Bộ nhớ: 256 MB.

Sample Input 1

3 4 3
2 1
2 4
3 3

Sample Output 1

6

Giải thích

Xóa dòng 1 → xóa cột 2 → còn ~2 \times 3 = 6~ ô.

Sample Input 2

4 4 4
2 1
3 4
4 1
4 4

Sample Output 2

6

Giải thích

Xóa cột 2 → xóa cột 3 cũ → xóa dòng 1 → còn ~3 \times 2 = 6~ ô.

Nguồn: LuyenCode.