Problem Description
You are given a directed graph with n vertices, labeled 1 to n. The edges of the graph contain values, and each time you traverse an edge, the value of that edge you traverse was added to your total score. If the same edge is traversed multiple times, its value was added every time. Values can be any number between -499 and 499, inclusive. There are no edges that connect a vertex to itself.
There's an ant at vertex 1 and it wants to get to vertex n. It must do this in an integer number of seconds between Tmin and Tmax, inclusive. The ant must make exactly one step each second, where each step consists of moving from its current vertex V to an adjacent vertex W (W is adjacent to V if there's a directed edge from V to W in the graph). The ant's goal is to get the highest score possible.
Input
There are multiple test cases.
For each test case, the first line contains three integers, n, Tmin and Tmax (2<=n<=50, 1<=Tmin<=Tmax<=1000000000).
Following n lines, shows an n*n matrix. The element aij (-499<=aij<=499) which in the i-th row and j-th column indicates an edge from the vertex i to vertex j values aij. If the aij equals to -500, means such edge didn’t exist. The elements in the diagonal are always -500, which means aii=-500 all the time.
Output
For every test case, output one line, means the max score the ant can get. If it’s impossible to get to vertex n, output ‘IMPOSSIBLE’.
Sample Input
2 3 6
-500 1
1 -500
Sample Output
5
