Trên một thanh gỗ được đánh tọa độ nguyên bắt đầu từ 1,2,3… (đơn vị độ dài) có một đàn kiến được chia ra thành ~ n ~ nhóm cùng nhau tìm kiếm thức ăn, trong đó nhóm thứ ~ i ~ ở tọa độ ~ x_i ~ có ~ a_i ~ con kiến. Nếu đặt một viên đường lên thanh gỗ, cả đàn kiến ngay tức khắc phát hiện và nhanh chóng di chuyển về vị trí có viên đường.

Yêu cầu: Hãy cho biết tổng quãng đường di chuyển ngắn nhất của đàn kiến khi đặt viên đường vào vị trí thích hợp.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~ n ~ ~ ( 1 ≤ n ≤ 10^6) ~
• Dòng thứ hai chứa ~ n ~ số nguyên ~ a_1, a_2, …, a_n ~ ~ (1 ≤ a_i ≤ 100, i = 1… n) ~
• Dòng thứ ba chứa ~ n ~ số nguyên ~ x_1, x_2, …, x_n ~ ~ (1 ≤ x_i ≤ 10^9, x_i < x_{i+1}, i=1…n ) ~

Kết quả

• Một số nguyên duy nhất là tổng quãng đường di chuyển.

Ràng buộc

• Có 30% số test có ~ 1 ≤ n ≤ 200 ~;
• Có 30% số test có ~ 200 < n ≤ 5000 ~;
• Có 40% số test ~ 5000 < n ≤ 10^6 ~;

Ví dụ:

Input 1

4
1 4 1 1
1 2 3 4 

Output 1

4