Mô tả và yêu cầu

Ở 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ánh nhiệm công việc đó đã đánh dấu cây hoa
được đánh giá là đẹ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ó 𝑛 cây hoa, với lề đường A cây hoa thứ 𝑖 được đánh giá bởi giá
trị là 𝑎𝑖, với lề đường B cây hoa thứ 𝑖 được đánh giá bởi giá trị là 𝑏𝑖 (với 𝑎𝑖 và 𝑏𝑖
nhận giá trị là 1 hoặc −1; 𝑖 = 1,2, … ,𝑛 ).
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 từ thiết bị nhập chuẩn:
 Dòng đầu tiên chứa số nguyên dương 𝑛(𝑛 ≤ 103);

 Trong 𝑛 dòng tiếp theo, dòng thứ 𝑖(1 ≤ 𝑖 ≤ 𝑛) chứa cặp số nguyên 𝑎𝑖 và 𝑏𝑖
cách nhau một khoảng trắng.
Kết quả: ghi ra thiết bị xuất chuẩn chứa một số nguyên duy nhất là số lượng cặp
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ụ

INPUT                                          OUTPUT
 5                                                4
 -1 -1
 1 1

 1 -1
 -1 -1
 -1 1
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