Sau một cuộc thí nghiệm, MH khám phá ra ~n~ loài sinh vật mới. Sinh vật thứ ~i~ có độ nguy hiểm ~a_i~ và chi phí cách ly là ~b_i~, với mỗi ~i<j~ thì ~a_i \leq a_j~ và ~b_i \geq b_j~. Cô ấy cần cách ly ~n~ sinh vật này, tuy nhiên, vì vấn đề kinh phí, MH sẽ phải cách ly những sinh vật này thành từng nhóm liên tiếp nhau từ trái sang phải. Chi phí để cách ly một nhóm sinh vật với ~i~ là sinh vật đầu nhóm, ~j~ là sinh vật cuối nhóm là ~a_i * b_j + b_i^2 * a_j^2~. Vì trước giờ chỉ học mỗi sinh nên MH không biết phải chia nhóm như nào để tốn ít chi phí nhất, các bạn hãy giúp cô ấy nhé!</p>

INPUT

• Dòng đầu tiên gồm ~1~ số nguyên dương ~n ( n \leq 10^6)~ .
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i(a_i \leq 10^6)~ .
• Dòng thứ ba gồm ~n~ số nguyên dương ~b_i(b_i \leq 10^3)~.

OUTPUT

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

Sample Input

7
2 5 5 8 13 15 19
20 17 15 7 4 4 4

Sample Output

17960

Subtask

• Subtask 1: ~b_i = 1~ (7p)
• Subtask 2: ~n \leq 10^3~ (28p)
• Subtask 3: ~n \leq 10^6~ (35p)

Giải thích

• 1 cách chia nhóm để có chi phí là 17960, chia làm 4 nhóm :
• Nhóm 1 bao gồm 1 với chi phí là 1640
• Nhóm 2 bao gồm 2-> 3 với chi phí là 7300
• Nhóm 3 bao gồm 4 với chi phí là 3192
• Nhóm 4 bao gồm 5->7 với chi phí là 5828
• 1640+7300+3192+5828=17960