cho.sh

So Sleepy

Find the longest total time asleep on one train while traveling from a start station and time to an appointment station by a deadline.

Medium6GraphShortest pathDynamic programmingNo attempts yetTime limit8sMemory limit512 MB

Problem

You are meeting a friend today, and you are very sleepy because you slept badly last night.

You go to the station of the appointment by train, so you can sleep on a train. You fall asleep the moment you board and stay asleep until you get off, and on the whole trip you can sleep on one train only.

Given a train timetable, your departure station and time, and the station and time of the appointment, write a program that prints the longest time you can sleep on a train while still reaching the appointment station by the appointed time.

Input

The input consists of several datasets. Each dataset has this form.

S T
D TimeD A TimeA
N1
K(1,1) Time(1,1)
...
K(1,N1) Time(1,N1)
N2
K(2,1) Time(2,1)
...
K(2,N2) Time(2,N2)
...
NT
K(T,1) Time(T,1)
...
K(T,NT) Time(T,NT)

The first line has the number of stations SS and the number of trains TT (1≤S≤10001 \le S \le 1000, 0≤T≤1000 \le T \le 100). The second line has the departure station D, the departure time TimeD, the appointment station A, and the appointed time TimeA, in this order. Then come the timetables of the TT trains. The first line of the ii-th timetable has Ni, the number of stations that train stops at, and each of the next Ni lines has a station number K(i,j) and the time Time(i,j) at which the train stops there.

A station number is an integer from 1 to SS. A time is written as hh:mm, where hh runs from 00 to 23 and mm runs from 00 to 59.

The last line of the input has two zeros.

You may assume the following.

  • Every train stops at two stations or more.
  • No train stops at the same station twice.
  • A train needs at least one minute to go from one stop to the next.
  • All the times in a dataset belong to the same day.
  • A transfer takes no time, so you can board a train that leaves a station at the exact minute you arrive there.

Output

For each dataset, print one line. If you can reach the appointment station by the appointed time, print the longest sleep in minutes. Otherwise print impossible. Waiting at a station and staying awake on a train do not count as sleep, and a trip with no sleep at all counts as 0 minutes.