Một cuộc đua đường dài được thực hiện trên đường đua vòng tròn. Trên đường đua ban tổ chức bố trí ~N~ trạm xăng theo chiều kim đồng hồ, mỗi trạm cách nhau ~1~ km. Các trạm xăng được đánh số từ ~1~ đến ~N~. Tất cả xe đua do ban tổ chức cung cấp tiêu hao ~1~ lít xăng cho mỗi km đi được. Tại trạm xăng thứ ~i~, xe đua có thể đổ ~f_i~ lít xăng với thời gian đổ là ~c_i~ cho mỗi lít. Để tăng độ khó cho cuộc đua, ban tổ chức cho phép các tay đua được chọn điểm xuất phát là bất kỳ trạm xăng nào. Các tay đua phải đi được ~N~ km theo chiều kim đồng hồ để được tính là hoàn thành cuộc đua. Bạn hãy giúp các tay đua tìm thời gian ít nhất phải dành cho việc đổ xăng để hoàn thành cuộc đua hoặc cho biết không có cách nào để hoàn thành cuộc đua.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 2.10^5)~ là số lượng trạm xăng
• Dòng thứ hai chứa ~N~ số nguyên ~f_1, f_2,...,f_N~ ~(0 \le f_i \le 10^9)~ là số lít xăng có thể đổ tại trạm xăng thứ ~i~.
• Dòng thứ ba chứa ~N~ số nguyên ~c_1, c_2,...,c_N~ ~(0 \le c_i \le 10^9)~ là thời gian đổ ~1~ lít xăng tại trạm xăng thứ ~i~.

Kết quả

• In ra thời gian ít nhất phải dành cho việc đổ xăng để hoàn thành cuộc đua hoặc in ra ~-1~ nếu không có cách nào để hoàn thành cuộc đua.

Sample Input 1

3
3 3 3
3 2 1

Sample Ouput

3

Sample Input 2

3
3 1 0
10 5 0

Sample Ouput

25

Sample Input 3

3
1 1 0
1 1 0

Sample Ouput

-1

Chấm điểm

• Subtask 1 (30% số test): ~N \le 2000~
• Subtask 2 (70% số test): Không có ràng buộc gì thêm

Giải thích

• Ở test thứu nhất, các tay đua xuất phát ở trạm xăng 3 và đổ 3 lít xăng tại trạm sạc này/ Thời gian đổ xăng là 3 x 1 = 3
• Ở test thứ hai, các tay đua xuất phát ở trạm xăng 1 và đổ 2 lít xăng tại trạm xăng này. Khi đến trạm xăng 2, các tay đua đổ thêm 1 lít xăng. Thời gian đổ xăng là ~2~ x ~10 + 1~ x ~5 = 25~
• Ở test thứ ba, không thể hoàn thành cuộc đua vì tổng số xăng ở các trạm xăng không đủ để đi được ~3~ km