Problem ID:
chem
Points:
2 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Author:
Problem type
Nhà hóa học ~Neko~ đã dành cả đời để nghiên cứu và đã tạo ra được một loại dung dịch mới có thể giải quyết hầu hết vấn đề của chúng ta hiện nay. Vấn đề duy nhất là ông đã đầu tư toàn bộ tài sản cho việc nghiên cứu nên chỉ có thể tạm chứa dung dịch ấy trong ~N~ ~(2 \le N \le 10^5)~ lọ ~anilin~ có sẵn. ~Neko~ sẽ rót những lọ anilin vào nhau và dùng những lọ trống để chứa dung dịch mới này.
Tuy vậy anilin là chất độc đối với con người nên sau khi tìm được những lọ trống thì ~Neko~ sẽ dùng dung dịch ~HCl~ để rửa sạch các lọ theo phương trình:
- ~C_6H_5NH_2 + HCl → C_6H_5NH_3Cl~ (muối không độc)
Vậy vấn đề làm sạch lọ có vẻ không mấy khó khăn, bạn hãy giúp ~Neko~ tìm cách rót các lọ anilin sao cho số lọ trống là nhiều nhất có thể.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~N~.
- ~N~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~a_i~ và ~b_i~ lần lượt là số ~ml~ anilin hiện có và dung tích tối đa của lọ thứ ~i~ ~(a_i \le b_i)~.
Kết quả
- Dòng đầu tiên là số lọ trống lớn nhất có thể có.
- Dòng thứ ~2~ gồm ~N~ số, số thứ ~i~ là lượng anilin mà lọ thứ ~i~ chứa sau khi rót. Mỗi số cách nhau một khoảng trắng.
Ràng buộc
- ~ 1 \le a_i \le b_i \le 10^9~.
- Subtask ~1~ ~(50\%)~: ~1 \le N \le 10^3~.
- Subtask ~2~ ~(50\%)~: ~10^3 < N \le 10^5~.
Ví dụ
Dữ liệu vào
3
1 5
3 5
2 5
Kết quả
1
5 1 0
Comments