Fewest sprinklers: hints, no solution

A row of garden beds is numbered 1 to m. Sprinkler i is fixed at bed positions[i] and waters every bed within reaches[i] beds on either side, including its own, so it covers beds positions[i] - reaches[i] through positions[i] + reaches[i]. A sprinkler may sit outside the row, and several may share a position. Return the fewest sprinklers that together water every bed from 1 to m, or -1 if some bed cannot be watered by the sprinklers available.

Examples

Input

m = 10, positions = [2, 6, 9, 4], reaches = [2, 1, 1, 3]

Output

2

Note

The sprinkler at 4 covers beds 1 to 7 and the one at 9 covers 8 to 10.

Input

m = 5, positions = [1, 5], reaches = [1, 0]

Output

-1

Note

Bed 3 and bed 4 are never watered.

Input

m = 4, positions = [0], reaches = [10]

Output

1

Constraints

• 1 <= m <= 1000000
• 0 <= positions.length <= 100000, and reaches has the same length
• 0 <= positions[i] <= 1000000, 0 <= reaches[i] <= 1000000

Hint 1: a nudge

Look at the leftmost bed that is still dry. Which sprinklers could water it, and what do they have in common?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing