Statement

Valerio is robbing a bank, but an alarm started ringing as he was trying to break into the caveau. He needs to get out as fast as possible through the twisted sewer tunnels running nearby the bank. The police is already looking for him and has sent K patrols, indexed from 0 to K-1 to guard the manholes connected to the sewer system. There are N manholes, indexed from 0 to N-1 and M tunnels connecting pairs of them. Valerio's friend Filippo is waiting for him nearby manhole N-1, if he can reach it, he will escape safely. Valerio starts from manhole 0 and, every minute, he can choose to move to a manhole adjacent to the one he is in or to stay another minute under the same manhole. Each police patrol guard L_i manholes, indexed from 0 to L_i-1. Patrol i is initially guarding manhole H_i,0, every minute it moves from manhole H_i,j to manhole H_i,j+1, after reaching manhole H_i,L_i-1, it return to manhole H_i,0.