1110. Minimum Jumps to Reach Home (Implicit BFS)

A bug sits at position 0 on an infinite number line and wants to reach position 'target'. It may jump forward exactly a, or backward exactly b, but it cannot jump backward twice in a row and cannot land on any forbidden position or on a negative position. Return the minimum number of jumps to reach target, or -1 if impossible. The input is JSON {forbidden, a, b, target}.

Input: JSON {forbidden, a, b, target}.

Output: Integer — minimum jumps, or -1.

Examples

Input: {"forbidden":[14,4,18,1,15],"a":3,"b":15,"target":9}
Output: 3
Explanation: Three jumps reach 9.

Input: {"forbidden":[8,3,16,6,12,20],"a":15,"b":13,"target":11}
Output: -1
Explanation: Target unreachable.

Input: {"forbidden":[],"a":3,"b":2,"target":6}
Output: 2
Explanation: Two forward jumps.

Constraints

• 1<=a,b<=2000
• 1<=target<=2000

Asked by