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* × *n* matrix *M*,
where for every pair (*i*, *j*) with *i* ≠ *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 → 1 → 3 → 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 ≤ *n* ≤ 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.

Public test cases

**Input**

6 0 20 5 -3 80 -2 11 0 30 -10 -12 3 22 -10 0 -50 15 -5 23 -60 35 0 90 7 97 14 -70 -11 0 -11 1 2 3 4 5 0

**Output**

100

**Input**

1 0

**Output**

0

**Input**

3 0 -6 8 -4 0 9 -7 -2 0

**Output**

9

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++