Ở thành phố tương lai, con người đã bắt đầu đi du lịch giữa 9 tầng mây.

Hiện tại, có 9 tầng mây, mỗi tầng có một số khách du lịch. Khách du lịch \(i\) đang ở tầng mây \(a_i\) và muốn đi tới tầng mây \(b_i\). Việc đi lại giữa các tầng mây phải thông qua một khinh khí cầu. Do số tiền bỏ ra để chế tác các đám mây là quá lớn và không đủ kinh phí để trùng tu phương tiện, khinh khí cầu chỉ chở được tối đa 4 hành khách. Và vì số lượng hạn hẹp, người khách \(i\) phải được lên khinh khí cầu trước người khách \(i+1\), nhưng khi đã ở trong khinh khí cầu, các vị khách có thể đi ra theo thứ tự bất kì.

Thời gian để khinh khí cầu đi lên một tầng hoặc xuống một tầng là 1. Thời gian để một người khách đi vào khinh khí cầu là 1. Thời gian để một người khách đi ra khỏi khinh khí cầu là 1. Hiện tại, khinh khí cầu đang ở tầng 1. Hãy tính thời gian ít nhất để khinh khí cầu đưa tất cả mọi người đến với tầng mây mong muốn nhé. Lưu ý rằng, khinh khí cầu không cần phải quay lại tầng 1 sau khi hoàn thành nhiệm vụ.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(n\) là số khách du lịch.
• \(n\) dòng sau, dòng \(i\) chứa 2 số nguyên dương \(a_i\) và \(b_i\) (\(a_i \neq b_i\), \(1 \leq a_i, b_i \leq 9\)).

Output

• Một số nguyên là thao tác ít nhất.

Example

3
1 2
1 3
1 4

9

2
1 2
2 1

6

Scoring

• \(33\%\) test có \(1 \leq n \leq 3\).
• \(67\%\) test có \(1 \leq n \leq 2000\).