Chi phí đốn cây

Có $n$ cây trong rừng, cây thứ $i$ có chiều cao $a_i$. Bạn cần đốn hạ hoàn toàn tất cả các cây bằng một chiếc cưa máy.

Mỗi lần dùng cưa lên cây thứ $i$, chiều cao của cây đó giảm đi $1$ đơn vị. Một cây được coi là đốn hạ hoàn toàn khi chiều cao của nó bằng $0$.

Cưa máy chỉ dùng được đúng một nhát cho mỗi lần sạc. Ban đầu cưa đã được sạc sẵn nên nhát cưa đầu tiên không tốn chi phí, còn trước mỗi nhát cưa tiếp theo bạn phải sạc lại cưa. Chi phí của một lần sạc phụ thuộc vào các cây đã bị đốn hạ hoàn toàn tại thời điểm đó: nếu $i$ là chỉ số lớn nhất trong số các cây đã bị đốn hạ hoàn toàn thì lần sạc đó tốn $b_i$. Nếu chưa có cây nào bị đốn hạ hoàn toàn thì không thể sạc cưa.

Dữ liệu đảm bảo $a_1=1$ và $b_n=0$, đồng thời $a_1<a_2<\dots <a_n$ và $b_1>b_2>\dots >b_n$.

Hãy tính tổng chi phí sạc nhỏ nhất để đốn hạ hoàn toàn tất cả $n$ cây.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa $n$ số nguyên $b_1,b_2,\dots ,b_n$.

Dữ liệu ra

Một số nguyên duy nhất: tổng chi phí sạc nhỏ nhất để đốn hạ hoàn toàn tất cả các cây.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^9$
• $0\le b_i\le {10}^9$
• $a_1=1$, $b_n=0$
• $a_1<a_2<\dots <a_n$ và $b_1>b_2>\dots >b_n$
• Kết quả có thể lên tới ${10}^{18}$, cần dùng kiểu số nguyên 64 bit.

Ví dụ