Given a directed and complete graph with *n* vertices,
and an initial vertex *x*,
compute the maximum cost
of all the paths without repeated vertices that begin at *x*.
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 80, corresponding to the path 1 → 0 → 3, with cost −10 + 90 = 80.

**Input**

Input consists of several cases,
each one with 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* ≤ 18,
0 ≤ *x* < *n*,
that the diagonal has only zeros,
and that the rest of numbers are between −10^{6} and 10^{6}.

**Output**

For every case,
print the cost of the worst path without repeated vertices that begins at *x*.

Public test cases

**Input**

4 0 -10 30 90 -10 0 50 -12 -60 35 0 15 14 -70 -11 0 1 1 0 0 3 0 6 8 -4 0 3 -7 -2 0 2

**Output**

80 0 0

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Dotzè Concurs de Programació de la UPC - Final
- Date
- 2014-10-01