Kiến trúc sư Hrvoje được giao vẽ một bức tường lớn không đều, được tạo thành từ các cột thẳng đứng.

Bức tường gồm ~n~ cột đặt sát nhau. Cột thứ ~i~ có chiều cao ~a_i~ và chiều rộng bằng ~1~. Để bản vẽ trở nên phức tạp hơn, cột thứ ~i~ được chia thành ~b_i~ phần có chiều cao bằng nhau.

Hrvoje chỉ có một cây thước và một cây bút chì. Với một nét vẽ, ông có thể vẽ đúng ~1~ đoạn thẳng mà không được nhấc bút lên. Mục tiêu là vẽ toàn bộ bức tường, bao gồm các cạnh của từng cột và toàn bộ các đường phân chia bên trong mỗi cột, bằng số đoạn thẳng ít nhất có thể.

Hãy tính số đoạn thẳng nhỏ nhất cần vẽ để hoàn thành bản vẽ.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~, với ~1 \le n \le 10^5~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~, với ~1 \le a_i \le 10^9~.

Dòng thứ ba chứa ~n~ số nguyên ~b_i~, với ~1 \le b_i \le 10^9~.

Output

In ra trên dòng duy nhất một số nguyên: số đoạn thẳng ít nhất mà Hrvoje cần vẽ để vẽ xong bức tường.

Chấm điểm

• Subtask ~1~ (~11~ điểm): ~n = 1~
• Subtask ~2~ (~13~ điểm): ~n = 2~, ~1 \le a_i, b_i \le 10~
• Subtask ~3~ (~29~ điểm): ~1 \le a_i \le 10^6~, và ~b_i \mid a_i~ với mọi ~1 \le i \le n~
• Subtask ~4~ (~57~ điểm): Không có ràng buộc bổ sung.

Sample Input ~1~

3
4 6 4
2 3 4

Sample Output ~1~

10

Sample Input ~2~

3
4 6 3
3 3 2

Sample Output ~2~

12

Giải thích

• Ví dụ ~2~: Hrvoje có thể kéo dài đoạn thẳng trên cùng của cột đầu tiên sang cột thứ hai, nhờ đó gộp ~2~ đoạn thành ~1~. Ông cũng làm tương tự với ~3~ đoạn ở sát đáy bức tường. Tổng cộng cần ~12~ đoạn thẳng, và có thể chứng minh đây là đáp án nhỏ nhất.