A. Truck-Kun
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Truck-Kun is traversing the complex metropolis of Tokyo. Tokyo is represented by a graph with $$$N$$$ ($$$1 \le N \le 300$$$) nodes. There is a directed edge between every pair of nodes, each having some amount of people on it. $$$w_{i,j}$$$ ($$$-10^9 \le w_{i, j} \le 10^9$$$). denotes the amount of people on the edge going from node $$$i$$$ to node $$$j$$$ (yes, there can be negative people). Since Truck-Kun wants to be a helpful truck, he wants to pick up as many people as possible by traversing through a simple path in the graph. A simple path of length $$$K$$$ is defined as a list of distinct nodes $$$a_1, a_2, \ldots, a_K$$$. The amount of people on a simple path is defined as $$$\sum_{i=1}^{K-1} w_{a_i,a_{i+1}}$$$. Since Truck-Kun knows this problem is hard, he only wants you to estimate the maximum amount of people that he can pick up by traversing through a simple path. Your answer will be considered correct if it is at least half of the true maximum. Formally, if $$$v$$$ is the true maximum and your code outputs $$$x$$$, it will be considered correct if $$$x \ge \frac{v}{2}$$$.

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 300$$$).

The next $$$N$$$ lines each contain $$$N$$$ integers. The integer on the $$$i$$$-th row and $$$j$$$-th column denotes $$$w_{i, j}$$$ ($$$-10^9 \le w_{i, j} \le 10^9$$$).

Output

Output a single integer $$$x$$$ ($$$0 \le x \le 10^{18}$$$), denoting an estimate of the maximum amount of people that Truck-Kun can pick up by traversing through a simple path. Your answer will be considered correct if it is at least half of the true maximum. Formally, if $$$v$$$ is the true maximum and your code outputs $$$x$$$, it will be considered correct if $$$x \ge \frac{v}{2}$$$.

Example
Input
4
0 -10 -10 6
-10 0 10 -10
-10 -10 0 -10
-10 -5 1 0
Output
11
Note

In the samples, an optimal simple path is $$$1$$$, $$$4$$$, $$$2$$$, $$$3$$$. This path contains $$$w_{1, 4} + w_{4, 2} + w_{2, 3} = 1 - 5 + 10 = 11$$$ people.