## Travelling Merchant's Friend

Points: 12 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type

You are friends with a travelling merchant, and you are travelling on a directed acyclic graph with nodes and edges. The fact that it is acyclic means that it is impossible to start at a node, travel along a valid path of positive length, and return to the starting node.

You were hoping to visit the travelling merchant. You are at node , and the travelling merchant is at node . At each node, you must maintain a nonnegative integer value. Your value determines which edges you can use and how your value changes each time you travel through an edge.

Each edge can be represented as five nonnegative integers: . This means that you may be able to travel from node to node . Let your current value be . After travelling from node to node , your value will change as such:

In other words, if your value is at least , your value increases by . Otherwise, it decreases by . Note that the value you maintain must be nonnegative. This means that if travelling along an edge would decrease your value to a negative number, you cannot travel along that edge.

Find the minimum starting value such that you can travel along some valid path from node to node .

#### Constraints

.

The graph is a simple path:

#### Input Specification

The first line of input contains two space-separated integers: and .

The next lines contain 5 space-separated integers: .

#### Output Specification

Output the minimum starting value that allows you to travel from node to node .

If it is impossible to reach node regardless of the starting value, output Impossible.

#### Sample Input 1

5 6
2 3 3 1 1
1 5 3 2 3
4 5 1 1 3
1 2 2 0 1
2 4 4 4 1
3 4 1 0 3

#### Sample Output 1

2

#### Explaination for Sample Output 1

Node Value Edge Taken

#### Sample Input 2

4 2
1 2 2 3 2
4 3 0 1 1

#### Sample Output 2

Impossible

#### Explaination for Sample Output 2

It is Impossible to travel from node to node on the given graph.