Ở thành phố nọ, để trang trí con đường tham quan nhân dịp các ngày lễ, lãnh đạo thành phố đã chỉ đạo trồng những cây hoa ở hai bên lề đường (có thể xem là lề đường A và lề đường B). Sau một thời gian, các cây hoa này đã trưởng thành và có thể phục vụ cho du khách tham quan. Trước dịp tết vừa qua, người ta thấy trong các cây hoa được trồng thì cũng có khá nhiều cây hoa không được đẹp nên lãnh đạo thành phố quyết định đưa ra phương án bỏ đi một số cây hoa và sắp xếp lại sao cho cảnh quan được hài hòa hơn. Người chịu trách nhiệm công việc đó đã đánh giá các cây hoa đẹp có số 1, còn các cây hoa được coi là xấu được đánh dấu là số -1. Việc bỏ đi các cây hoa xấu có thể làm cho con đường tham quan không còn nhiều cây hoa nữa nên công việc ở đây cần làm phải đảm bảo tất cả các điều kiện sau:
- Không được di chuyển cây hoa ở lề đường A sang lề đường B và ngược lại;
- Các cây hoa trên cùng một lề đường không được thay đổi vị trí với nhau;
- Một cây hoa ở lề đường A và một cây hoa ở lề đường B sẽ tạo thành 1 cặp;
- Với một cặp được giữ lại phải luôn luôn không được có 2 cây hoa cùng xấu;
- Số lượng cây hoa được giữ lại là nhiều nhất.
Mỗi lề đường đều có \( n \) cây hoa, với lề đường A cây hoa thứ \( i \) được đánh giá bởi giá trị là \( a_i \), với lề đường B cây hoa thứ \( i \) được đánh giá bởi giá trị là \( b_i \) (với \( a_i \) và \( b_i \) nhận giá trị là hoặc -1, hoặc 1, \( i = 1, 2, ..., n \)).
Yêu cầu:
Cho biết số lượng cặp cây hoa được giữ lại nhiều nhất thỏa mãn tất cả các điều kiện nêu trên là bao nhiêu?
Dữ liệu:
Vào
- Dòng đầu tiên chứa số nguyên dương \( n \) (\( n \leq 10^3 \));
- Trong \( n \) dòng tiếp theo, dòng thứ \( i \) (\( 1 \leq i \leq n \)) chứa cặp số nguyên \( a_i \), \( b_i \) cách nhau một khoảng trắng.
Kết quả:
Ghi ra một số nguyên duy nhất là số lượng cây hoa nhiều nhất được giữ lại thỏa mãn tất cả các điều kiện của đề bài.
Ví dụ:
INP
5
-1 -1
1 1
1 - 1
-1 -1
- 1 1
OUT
4
Giải thích:
Chọn được nhiều nhất là 4 cặp cây hoa:
- Lề đường A: gồm các cây ở vị trí 1, 2, 3, 4
- Lề đường B: gồm các cây ở vị trí 2, 3, 4, 5
Bình luận