Chú ếch Gorf đang du hành qua vương quốc Đầm Lầy. Thật không may, sau một cú nhảy tồi, chú đã rơi xuống một cái giếng sâu ~n~ mét. Bây giờ Gorf đang ở đáy giếng và có một chặng đường dài để leo lên.

Bề mặt tường giếng có chất lượng khác nhau: có chỗ trơn trượt, nhưng có chỗ lại có gờ đá thuận tiện. Nói cách khác, nếu Gorf đang ở độ sâu ~x~ mét so với mặt đất, thì trong một cú nhảy, chú có thể nhảy lên một khoảng cách nguyên bất kỳ từ ~0~ đến ~a_x~ mét (lưu ý rằng Gorf không thể nhảy xuống, chỉ có thể nhảy lên).

Thật không may, Gorf phải nghỉ ngơi sau mỗi cú nhảy (kể cả cú nhảy ~0~ mét). Và sau khi nhảy lên vị trí ~x~ mét dưới mặt đất, chú sẽ bị trượt xuống đúng ~b_x~ mét trong khi nghỉ ngơi.

Hãy tính số lần nhảy tối thiểu Gorf cần để chạm tới mặt đất.

Input

Dòng đầu tiên chứa một số nguyên duy nhất ~n~ ~(1 \le n \le 300000)~ - độ sâu của giếng.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le i)~, trong đó ~a_i~ là chiều cao tối đa Gorf có thể nhảy từ độ sâu ~i~ mét dưới mặt đất.

Dòng thứ ba chứa ~n~ số nguyên ~b_1, b_2, \dots, b_n~ ~(0 \le b_i \le n - i)~, trong đó ~b_i~ là khoảng cách Gorf sẽ bị trượt xuống nếu chú nghỉ ngơi ở độ sâu ~i~ mét dưới mặt đất.

Output

Nếu Gorf không thể chạm tới mặt đất, in ra ~-1~. Ngược lại, hãy in ra số nguyên duy nhất ~k~ - số lần nhảy tối thiểu có thể.

Scoring

Sample Input 1

3
0 2 2
1 1 0

Sample Output 1

2

Sample Input 2

2
1 1
1 0

Sample Output 2

-1

Sample Input 3

10
0 1 2 3 5 5 6 7 8 5
9 8 7 1 5 4 3 2 0 0

Sample Output 3

3

Notes

Test 1: Gorf đang ở đáy giếng và nhảy lên độ cao ~1~ mét dưới mặt đất. Sau đó, chú bị trượt xuống ~1~ mét và dừng lại ở độ cao ~2~ mét dưới mặt đất. Bây giờ, từ đây, chú có thể chạm tới mặt đất trong một cú nhảy.

Test 2: Gorf có thể nhảy lên độ cao ~1~ mét dưới mặt đất, nhưng sẽ bị trượt trở lại đáy giếng. Đó là lý do chú không thể chạm tới mặt đất.

Test 3: Gorf có thể chạm tới mặt đất chỉ từ độ cao ~5~ mét dưới mặt đất. Và Gorf có thể đạt được độ cao này bằng một chuỗi các cú nhảy ~10 \Rightarrow 9 \dashrightarrow 9 \Rightarrow 4 \dashrightarrow 5~, trong đó ~\Rightarrow~ là cú nhảy và ~\dashrightarrow~ là trượt trong khi nghỉ.