Khai Thác Gỗ

Có $n$ cái cây với chiều cao $a_1,a_2,\dots ,a_n$. Bạn cần chặt tất cả các cây xuống chiều cao $0$ bằng một cái cưa máy.

• Mỗi lần dùng cưa máy lên cây thứ $i$, chiều cao cây đó giảm đi $1$ đơn vị.
• Sau mỗi lần dùng cưa, cưa phải được sạc lại trước khi dùng tiếp.
• Chi phí mỗi lần sạc phụ thuộc vào cây có chỉ số lớn nhất đã bị chặt hoàn toàn (chiều cao bằng $0$): nếu chỉ số lớn nhất đó là $i$, chi phí một lần sạc là $b_i$.
• Nếu chưa có cây nào bị chặt hoàn toàn thì không thể sạc cưa.
• Cưa được sạc đầy ngay từ đầu (lần dùng đầu tiên không tốn chi phí).

Đã biết rằng $a_1=1$, $b_n=0$, dãy $a$ tăng ngặt và dãy $b$ giảm ngặt.

Hãy tính tổng chi phí tối thiểu để chặt sạch toàn bộ $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

In ra một số nguyên duy nhất — tổng chi phí tối thiểu để chặt sạch toàn bộ 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<\cdots <a_n$ và $b_1>b_2>\cdots >b_n$

Ví dụ