Bài toán xây hàng rào tối ưu chi phí sử dụng quy hoạch động Convex Hull Trick động với cây Li Chao.

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng 2: \(N\) số nguyên dương \(h_1, h_2, \dots, h_N\).
• Dòng 3: \(N\) số nguyên dương \(w_1, w_2, \dots, w_N\).

Định dạng đầu ra

• Một số nguyên duy nhất là chi phí tối thiểu.

Ví dụ

Input:

3
2 3 5
1 2 3

Output:

11

Giải thích: Chi phí tối thiểu để xây dựng các đoạn hàng rào liên kết.

Ràng buộc & Subtasks