Dãy Chuyển Tiếp Đơn Điệu

Cho hai dãy số nguyên $a_{1}, \dots, a_{n}$ và $b_{1}, \dots, b_{n}$ . Đặt $d p_{1} = 0$ . Với mỗi $i > 1$ , bạn phải chọn một chỉ số $j < i$ và trả chi phí $d p_{j} + b_{j} \cdot a_{i}$ .

Hãy tính giá trị nhỏ nhất có thể của $d p_{n}$ .

Input

Dòng đầu chứa $n$ .
Dòng thứ hai chứa dãy $a$ .
Dòng thứ ba chứa dãy $b$ .

Output

In $d p_{n}$ .

Constraints

$1 \leq n \leq 1 0^{5}$ .
$a_{1} = 1, 1 \leq a_{i} \leq 1 0^{9}$ và dãy $a$ tăng nghiêm ngặt.
$b_{n} = 0, 0 \leq b_{i} \leq 1 0^{9}$ và dãy $b$ giảm nghiêm ngặt.

Scoring

Subtask $1$ ( $50%$ số điểm): kích thước chính không vượt quá $60$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

4
1 2 4 7
9 6 3 0

Output

Giải thích: Ta có $d p_{2} = 18, d p_{3} = 36$ . Với $i = 4$ , ba lựa chọn cho giá trị $63, 60, 57$ , nên $d p_{4} = 57$ .

Lời giải tóm tắt

Phân tích: Tính recurrence cực tiểu tuyến tính trên mọi chỉ số trước.
Thuật toán: Mỗi trạng thái j sinh đường y=b_j·x+dp_j. Truy vấn bao dưới tại x=a_i để lấy dp_i, rồi thêm đường của trạng thái mới.
Chứng minh: Tập đường trước khi xử lý i tương ứng một-một với mọi j<i; giá trị đường tại a_i đúng bằng chi phí nếu chọn j. Vì vậy cực tiểu của bao là recurrence.
Độ phức tạp: O(n log n) thời gian, O(n) bộ nhớ.