Meeting Time (Bronze)#11188
Bessie and her sister Elsie want to travel from the barn to their favorite field. They want to leave the barn at exactly the same time and arrive at their favorite field at exactly the same time.
The farm consists of fields numbered , where field contains the barn and field is their favorite field. The farm is built on the side of a hill, with field being at a higher elevation than field whenever x < y. An assortment of paths connects pairs of fields. However, since each path is rather steep, it can only be traveled in the downhill direction. For example, a path connecting fields and can be traveled from to , but not in the opposite direction, since that would require traveling uphill. Each pair of fields is connected by at most one path, so m \leq n \cdot (n - 1) / 2.
Bessie and Elsie may take different amounts of time to travel along the same path. For example, Bessie might take units of time, while Elsie might take . Moreover, they only spend time traveling along paths between fields. Since they are in a hurry, they pass through each field in essentially zero time and never wait at any field.
Please help determine the minimum amount of time Bessie and Elsie need to reach their favorite field and arrive there at exactly the same moment.
The first line contains two integers, and m~(1 \le n \le 16).
Each of the following lines describes a path using four integers A, B, C, and , where and B~(A < B) are the fields connected by the path, is the time required for Bessie to travel along the path, and is the time required for Elsie to travel along the path. Both and are in the range .
Print one integer representing the minimum amount of time Bessie and Elsie need to travel to their favorite field and arrive there at exactly the same moment. If this is impossible, or if either Bessie or Elsie cannot reach the favorite field, print IMPOSSIBLE on a single line.
Bessie is twice as fast as Elsie on every path. However, if Bessie takes the path 1 \to 2 \to 3 and Elsie takes the path 1 \to 3, they will arrive at their destination at the same time.
Beispiel 1