Maximum cost of a path (2) P70102

Given a directed and complete graph with $n$ vertices, compute the maximum cost of all the paths with the vertices in increasing order. The given graph is represented by an $n \times n$ matrix $M$, where for every pair $(i, j)$ with $i \ne j$, $m_{ij}$ is the (perhaps negative) cost of the arc from $i$ to $j$.

For instance, the maximum cost of the first test is 100, because of the path $0 \to 1 \to 3 \to 4$, with cost $20 - 10 + 90 = 100$.

Input

Input consists of the number of vertices $n$, followed by the matrix $M$ ($n$ lines, each one with $n$ integer numbers), followed by the initial vertex $x$. Vertices are numbered from 0 to $n-1$. You can assume $1 \le n \le 10^3$, that the diagonal has only zeros, and that the rest of numbers are between $-10^6$ and $10^6$.

Output

Print the maximum cost of all the paths with the vertices in increasing order.