Một chú ốc sên nằm tại gốc tọa độ $(0,0)$ của hệ trục hai chiều. Trên trục $x$ có $n$ cây tre song song với trục $y$ , chân tre có tung độ bằng $0$ , hoành độ lần lượt là $x_1,x_2,\dots,x_n$ . Tre cao vô hạn, bề rộng không đáng kể.

Ốc sên cần đi từ gốc tọa độ đến chân cây tre thứ $n$ tại $(x_n, 0)$ , quy tắc di chuyển:

1. Chỉ có thể bò trên trục $x$ hoặc trên thân tre;

2. Tốc độ bò trên trục $x$ : $1$ đơn vị/giây;

3. Tốc độ bò lên trên thân tre: $0.7$ đơn vị/giây;

4. Tốc độ bò xuống trên thân tre: $1.3$ đơn vị/giây;

5. Cổng dịch chuyển ma thuật: giữa cây tre thứ $i$ và cây tre thứ $i+1$ tồn tại một cổng dịch chuyển ( $0<i<n$ ), ốc sên đứng tại $(x_i,a_i)$ có thể đến $(x_{i+1},b_{i+1})$ ngay lập tức.

Tìm thời gian ngắn nhất để ốc sên đến được đích (làm tròn giữ hai chữ số thập phân).

Dữ liệu vào

1. Dòng đầu tiên: số nguyên dương $n$ (số lượng cây tre);

2. Dòng thứ hai: $n$ số nguyên dương $x_1,x_2,\dots,x_n$ (hoành độ các cây tre);

3. $n-1$ dòng tiếp theo: mỗi dòng hai số nguyên dương $a_i,b_{i+1}$ (độ cao cổng dịch chuyển trên cây tre thứ $i$ , độ cao cổng dịch chuyển trên cây tre thứ $i+1$ ).

Dữ liệu ra

In ra một số thực, giữ hai chữ số thập phân.

Ví dụ

Input

3
1 10 11
1 1
2 1

Output

4.20

Ghi chú

Giải thích mẫu

Lộ trình tối ưu:

$(0,0) \to (1,0) \to (1,1) \to (10,1) \to (10,0) \to (11,0)$

Tính thời gian:

$1 + \frac{1}{0.7} + 0 + \frac{1}{1.3} + 1 \approx 4.20$

Phạm vi dữ liệu

• 20% dữ liệu: $n \leq 15$ ;

• 100% dữ liệu: $n \leq 10^5$ , $a_i,b_i \leq 10^4$ , $x_i \leq 10^9$ .