Dự trữ nước

Điểm số: 1

Giới hạn thời gian: 2s

Giới hạn bộ nhớ: 512 MB

Người đăng: admin

 Ở miền Trung thường năm nào cũng có những đợt hạn hán nên ông Nam có những thùng dự trữ nước. Do mưa làm nhiều đợt nên N (1 ≤ N ≤ 1000) thùng chứa nước của ông Nam có kích thước khác nhau, mỗi thùng có sức chứa Ci (1 ≤ Ci ≤ 10000, 1 ≤ i ≤ N). Dự đoán rằng năm nay sẽ có đợt hạn hán lớn nên ông Nam muốn đổ đầy nước hết các thùng để dự trữ. Sau khi kiểm tra ông Nam thấy rằng có một số thùng vẫn còn đầy, một số khác thì vơi đi một phần, còn một số thì đã hết. Ông quyết định các thùng nào chưa đầy thì sẽ chở đi để đổ đầy nước. Nhưng do nơi lấy nước rất xa, và mỗi lần chỉ chở đi được 1 thùng nên ông quyết định sẽ san nước giữa các thùng với nhau để số thùng phải chở đi là ít nhất

Yêu cầu: Cho dung lượng nước hiện có của thùng thứ i là Bi (0 ≤ Bi ≤ Ci, 1 ≤ i ≤ N), hãy giúp ông Nam xác định số lượng thùng ít nhất phải mang đi.

Dữ liệu vào:

• Dòng thứ nhất ghi một số tự nhiên N là số lượng các thùng nước.

• Dòng thứ i trong N dòng tiếp theo mỗi dòng có 2 số nguyên Bi và Ci (0 ≤ Bi ≤ Ci) mô tả thông tin thùng thứ i, với Bi là nước còn trong thùng và Ci là sức chứa của thùng, các số cách nhau ít nhất một khoảng trắng.

Kết quả:

In ra một số là số lượng ít nhất các thùng nước tìm được.

Ví dụ:

Input

Output

4

0 1

4 5

0 2

1 2

1