Tối ưu hóa quy hoạch động dạng \(dp[i] = \min_{j < i} (dp[j] + a_i \cdot b_j + c_i)\) bằng cấu trúc cây Li Chao.

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

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số \(a_1, a_2, \dots, a_N\).
• Dòng thứ ba chứa \(N\) số \(b_1, b_2, \dots, b_N\).

Định dạng đầu ra

• In ra giá trị \(dp[N]\) tối ưu.

Ví dụ

Input:

3
1 2 3
3 2 1

Output:

3

Giải thích: Tính giá trị quy hoạch động tối ưu tại bước cuối cùng.

Ràng buộc & Subtasks