Doge Message Relay

In Jakarta, there are N skyscrapers arranged in a row and numbered from 0 to N-1. There are also M mysterious creatures called doge residing in the city. The doges are numbered from 0 to M-1; doge i initially lives on skyscraper B_i and has a jump power of P_i > 0.

A doge located on skyscraper b with jump power p can, in one jump, move to either skyscraper b-p or b+p if the destination index lies in the range [0, N-1] (i.e. if 0 \leq b-p < N or 0 \le; b+p < N respectively).

Doge 0 (the leader) initially holds an urgent message that must be delivered as quickly as possible to doge 1. Any doge who has received the message may do one of the following:

• Jump to another skyscraper (this counts as one jump step).
• Pass the message to any other doge on the same skyscraper (this does not count as a jump).

The task is to determine the minimum total number of jumps required to deliver the message from doge 0 to doge 1, or determine that it is impossible to deliver the message.

Note: When a doge jumps, it moves from its current skyscraper to the destination, and if the destination skyscraper contains one or more doges (who are there initially), those doges can receive the message immediately without extra jumps.

The jump transitions from a skyscraper b using doge i's jump are given by:

\( b \to b - P_i \quad \text{or} \quad b \to b + P_i \quad \text{if valid.} \)

inputFormat

The input consists of three lines:

1. The first line contains two integers N and M, the number of skyscrapers and the number of doges respectively.
2. The second line contains M integers B₀, B₁, ..., B_M-1, where B_i is the initial skyscraper index of doge i.
3. The third line contains M integers P₀, P₁, ..., P_M-1, where P_i is the jump power of doge i.

Note: It is guaranteed that 0 \leq B_i < N for every i, and P_i > 0.

outputFormat

Output a single integer: the minimum number of jumps required to deliver the message from doge 0 to doge 1. If it is impossible to deliver the message, output -1.

sample

5 3
2 4 2
2 1 3

1