Đầu bếp giỏi là cuộc thi đầu bếp giỏi do Liên hiệp hội các khách sạn du lịch tổ chức. Mỗi thí sinh tham gia cuộc thi sẽ đăng ký dự thi vào một trong ~N~ ngày diễn ra cuộc thi. Vì vậy, ngày thứ ~i~ sẽ có ~a_i~ đầu bếp muốn dự thi, nhưng Ban tổ chức chỉ có khả năng cho ~b_i~ thí sinh dự thi.

Ban tổ chức muốn tất cả đầu bếp đăng ký tham gia cuộc thi đều được dự thi nên có thể phải chuyển thí sinh đăng ký ở ngày này sang dự thi vào ngày khác. Nếu đầu bếp đăng ký dự thi ngày ~i~ chuyển sang thi vào ngày ~j~ thì mức độ không hài lòng của đầu bếp này là ~|i-j|~.

Yêu cầu: Giúp Ban tổ chức cuộc thi sắp xếp lịch thi cho tất cả đầu bếp đều được dự thi sao cho ngày thứ ~i~ trong ~N~ ngày diễn ra cuộc thi có không quá ~b_i~ thí sinh dự thi và mức độ không hài lòng lớn nhất của các đầu bếp tham gia cuộc thi là nhỏ nhất.

Input

• Dòng thứ nhất chứa số nguyên ~N~ ~(1 \le N \le 10^6)~, là số ngày diễn ra cuộc thi.

• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~, với ~a_i~ là số đầu bếp muốn thi vào ngày thứ ~i~.

• Dòng thứ ba chứa ~N~ số nguyên dương ~b_1, b_2, \dots, b_N~ ~(0 \le b_i \le 10^9)~, với ~b_i~ là số đầu bếp tối đa có thể được thi vào ngày thứ ~i~.

Các số trên một dòng cách nhau ít nhất một dấu cách.

Output

Trong trường hợp sắp xếp được lịch dự thi cho tất cả đầu bếp thì xuất ra số nguyên ~K~ nhỏ nhất sao cho mức độ không hài lòng của các đầu bếp được tham gia dự thi không vượt quá ~K~. Nếu không sắp xếp được lịch thi cho tất cả đầu bếp thì ghi ~-1~.

Sample Input 1

4
6 14 70 1
70 3 16 5

Sample Output 1

2

Sample Input 2

1
3
2

Sample Output 2

-1