Open the Lock

A bike lock has four wheels, each showing a digit from 0 to 9, and it starts at '0000'. One turn moves one wheel one step up or down, and the wheels wrap around: one step up from 9 is 0, and one step down from 0 is 9. The codes in jams are traps: if the wheels ever show one of them, the lock jams for good, so you must never pass through them.

Write open_lock(jams, target) that returns the fewest turns that take the wheels from '0000' to target, or -1 if it cannot be done. If '0000' itself is in jams, the lock is jammed from the start.

Examples

open_lock(['0100', '0900'], '0200')  # returns 4
open_lock([], '9999')  # returns 4
open_lock(['1000', '9000', '0100', '0900', '0010', '0090', '0001', '0009'], '1111')  # returns -1

In the first example both ways of moving the second wheel straight to 2 are jammed, so you turn the first wheel to 1, move the second wheel up twice, and turn the first wheel back: 4 turns. In the last example every first turn jams the lock.

Constraints

• target is a string of four digits, and jams holds up to 5,000 such strings.