Info City là một thành phố đặc biệt: người dân thanh toán bằng đồng Infocoin, và các tờ tiền chỉ có mệnh giá là lũy thừa của ~2~, tức ~2^k~ với ~k = 0,1,2,3,\dots~.

Steve vừa được tăng lương nên ghé siêu thị điện máy mua một máy tính và các phần mềm bản quyền. Khi đến quầy thanh toán, Steve mới phát hiện quên ví ở nhà nên phải quay về lấy tiền. Quá bối rối, Steve chỉ nhớ rằng mình đã chọn ~n~ mặt hàng, và giá của mặt hàng thứ ~i~ là một số nguyên nằm trong đoạn ~[a_i, b_i]~.

Steve muốn mang theo ít tờ tiền nhất nhưng vẫn đảm bảo rằng: dù tổng tiền thực tế tại quầy là bao nhiêu (miễn là phù hợp với các khoảng giá đã nhớ), Steve vẫn có thể trả đúng bằng tổng đó (thu ngân không cần thối lại).

Yêu cầu

Hãy xác định số lượng tờ tiền tối thiểu cần mang theo sao cho với mọi cách chọn giá thực tế ~x_i \in [a_i,b_i]~ (với ~i=1..n~), Steve có thể chọn một số tờ trong các tờ đã mang để trả đúng tổng ~S = \sum_{i=1}^{n} x_i~.

Mỗi tờ tiền có mệnh giá thuộc tập ~{2^0,2^1,2^2,\dots}~ và Steve được phép mang nhiều tờ cùng mệnh giá.

Dữ liệu

• Dòng đầu tiên chứa số nguyên ~n~.
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~.

Kết quả

In ra một số nguyên: số lượng tờ tiền tối thiểu cần phải mang đi.

Ví dụ

Ví dụ 1

Input

4
3 5
7 9
2 4
1 10

Output

5

Ràng buộc và chấm điểm

• ~1 \le n \le 10^5~
• ~1 \le a_i \le b_i \le 10^9~