Có \(n\) cây cột đứng trên sông, xếp thành một hàng thẳng từ bờ này sang bờ kia. Chiều cao cột thứ \(i\) là \(h_i\). Ta muốn xây một cây cầu được đỡ bởi một số cột đã chọn; cột đầu tiên và cột cuối cùng bắt buộc phải được chọn. Nối đỉnh của mỗi cặp cột được chọn liên tiếp bằng một đoạn cầu.

Chi phí xây đoạn cầu nối cột \(i\) và cột \(j\) là \((h_i-h_j)^2\). Ngoài ra, mọi cột không được chọn phải bị dỡ bỏ để không cản trở giao thông trên sông. Chi phí dỡ cột thứ \(i\) là \(w_i\); giá trị này có thể âm vì có bên sẵn sàng trả tiền để cột bị dỡ.

Hãy chọn các cột làm trụ cầu sao cho tổng chi phí xây cầu và dỡ các cột còn lại là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(2\le n\le100000\)), là số cột.

Dòng thứ hai chứa \(n\) số nguyên \(h_i\) (\(0\le h_i\le10^6\)), là chiều cao các cột theo thứ tự.

Dòng thứ ba chứa \(n\) số nguyên \(w_i\) (\(-10^6\le w_i\le10^6\)), là chi phí dỡ từng cột.

Dữ liệu ra

In một số nguyên duy nhất là tổng chi phí nhỏ nhất. Kết quả có thể âm.

Ví dụ

6
3 8 7 1 6 6
0 -1 9 1 2 0

17

Phân nhóm

1. \(30\) điểm: \(n\le1000\).
2. \(30\) điểm: Phương án tối ưu có nhiều nhất \(2\) cột trụ bổ sung ngoài cột đầu và cột cuối; \(|w_i|\le20\).
3. \(40\) điểm: Không có ràng buộc bổ sung.