Air Pollution

In 20XX, the owners of the ICPC (Ikuta's Computer Pollutes Community) shopping district were suffering from air pollution. In order to regain the vitality of the past, the cleanliness of the atmosphere must be kept above a certain level.

The shops in the shopping district are lined up in a row and are numbered from 1 to n. Currently, the cleanliness of the atmosphere around each store is pi. You can change the cleanliness of the atmosphere in that store and the surrounding stores by choosing the 2nd to n-1st stores and circulating the air around them. To be precise, when the i (2 ≤ i ≤ n−1) th is selected, only pi is added to pi−1 and pi + 1, and conversely, only 2 pi is subtracted from pi. In other words, the new cleanliness of the atmosphere p'is,

• p'i−1 = pi−1 + pi
• p'i = pi − 2 pi
• p'i + 1 = pi + 1 + pi. The purpose is to repeat this operation to make the air cleanliness pi of all stores equal to or greater than the minimum acceptable air cleanliness li.

It costs a lot to circulate the atmosphere, so we want to achieve it as few times as possible. I want you to help us for the future of the ICPC shopping district.

Input

The input is given in the following format.

n p1 ... pn l1 ... ln

n is the number of stores, pi is the current clean air of the i-th store, and li is the clean air that the i-th store should achieve.

Constraints

Each variable being input satisfies the following constraints.

• 3 ≤ n ≤ 105
• −108 ≤ pi ≤ 108
• 1 ≤ li ≤ 108

Output

Output the minimum number of air circulations required by all stores to achieve clean air in one line.

If you cannot achieve it no matter how you operate it, output -1.

Examples

Input

3 3 -1 4 2 1 3

Output

1

Input

3 3 -1 4 2 1 5

Output

-1

Input

4 3 -1 -1 3 1 1 1 1

Output

3

inputFormat

Input

The input is given in the following format.

n p1 ... pn l1 ... ln

n is the number of stores, pi is the current clean air of the i-th store, and li is the clean air that the i-th store should achieve.

Constraints

Each variable being input satisfies the following constraints.

• 3 ≤ n ≤ 105
• −108 ≤ pi ≤ 108
• 1 ≤ li ≤ 108

outputFormat

Output

Output the minimum number of air circulations required by all stores to achieve clean air in one line.

If you cannot achieve it no matter how you operate it, output -1.

Examples

Input

3 3 -1 4 2 1 3

Output

1

Input

3 3 -1 4 2 1 5

Output

-1

Input

4 3 -1 -1 3 1 1 1 1

Output

3

样例

3
3 -1 4
2 1 3

1