Đế Chế Quảng Cáo

Xem dạng PDF

Gửi bài giải


Điểm: 0,01
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tại một thành phố nọ, có một dãy gồm ~n~ bức tường hình chữ nhật nằm liền kề nhau, không có khoảng trống và có cạnh dưới cùng nằm trên một đường thẳng nằm ngang. Các bức tường được đánh số từ ~1~ đến ~n~ theo thứ tự từ trái sang phải. Bức tường thứ ~i~ có chiều rộng ~w_i~ và chiều cao ~h_i~.

Trong khi người qua đường chỉ thấy một dãy tường, Shidou lại thấy cơ hội khởi nghiệp. Cậu lập tức thuê toàn bộ mặt tường, quyết tâm phủ kín nó bằng poster quảng cáo. Theo kế hoạch, đây sẽ là bước đầu tiên để xây dựng một đế chế quảng cáo.

Vấn đề là mỗi tấm poster đều tốn tiền. Dãy tường thì dài, ngân sách thì hạn hẹp, nên Shidou phải tìm cách dùng ít poster nhất có thể mà vẫn phủ kín toàn bộ mặt tường.

Việc dán poster phải tuân thủ các quy định sau:

  • Mỗi poster là một hình chữ nhật có kích thước tùy ý, với các cạnh nằm ngang hoặc thẳng đứng.

  • Một poster có thể phủ qua nhiều bức tường liền kề, nhưng phải nằm hoàn toàn trong mặt tường.

  • Các poster không được chồng lên nhau, nhưng có thể chạm nhau hoặc dùng chung cạnh.

  • Tất cả các poster phải cùng nhau phủ kín toàn bộ mặt tường.

Hãy tính số lượng poster ít nhất mà Shidou cần sử dụng, để đế chế quảng cáo kịp ra đời trước khi founder phải đi xin hoàn tiền thuê tường.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~1 \leq n \leq 10^6~) — số lượng bức tường trong dãy tường.

Mỗi dòng trong ~n~ dòng tiếp theo chứa ~w_i, h_i~ (~1 \leq w_i, h_i \leq 10^9~) lần lượt là chiều rộng và chiều cao của bức tường thứ ~i~.

Output

In ra một số nguyên duy nhất là số lượng poster ít nhất cần phải sử dụng.

Sample Input 1

5
1 2
1 3
2 2
2 5
1 4

Sample Output 1

4

Notes

image

Hình trên thể hiện chiều rộng và chiều cao của các bức tường trong ví dụ. Hình dưới minh họa cách phủ kín dãy tường bằng ~4~ tấm poster.


Đang tải...