Se realizará pronto un torneo de ping pong, en la modalidad dobles: varios equipos, cada uno de 2 jugadores, se enfrentarán entre sí.

El torneo forma parte de un evento benéfico especial, en el cual los equipos de jugadores se forman emparejando entre sí a los mejores ~N~ jugadores del país. Para los fines de coordinación del torneo, estos jugadores se numeran desde ~1~ hasta ~N~.

Los organizadores buscan maximizar el interés del evento resultante, y eso depende de las parejas formadas. Por cada par de jugadores ~i~ y ~j~, se conoce un valor ~a_{i,j}~ que indica qué tan interesante sería para el público ver competir juntos en un equipo a los jugadores ~i~ y ~j~.

El interés total del evento será la suma de los valores ~a_{i,j}~ correspondientes a los ~\frac{N}{2}~ equipos en los cuales se dividan los ~N~ jugadores.

Debes escribir un programa que dado el valor de ~N~ y los valores ~a_{i,j}~, determine el máximo interés posible del evento.

Entrada

Se recibe de la entrada estándar en una primera línea, el entero ~N~.

Luego ~N~ líneas más, cada una con ~N~ enteros separados por espacios. El entero ~j~ de la línea ~i~ indica el valor ~a_{i,j}~.

Salida

Se debe escribir a la salida estándar una única línea con un único entero: el máximo interés posible del torneo.

Ejemplo

4
0 2 9 5
2 0 4 1
9 4 0 2
5 1 2 0

Salida de Ejemplo

10

Las siguientes son todas las maneras posibles de armar los equipos para este ejemplo:

• 1-2 y 3-4 : Beneficio ~2 + 2 = 4~
• 1-3 y 2-4 : Beneficio ~9 + 1 = 10~
• 1-4 y 2-3 : Beneficio ~5 + 4 = 9~

Restricciones

• ~2 \leq N \leq 30~
• ~0 \leq a_{i,j} \leq 10^8~
• ~a_{i,i} = 0~ para ~1 \leq i \leq N~
• ~a_{i,j} = a_{j,i}~
• ~N~ siempre es par

Subtareas

1. (10 puntos) ~N \leq 8~

2. (20 puntos) ~N \leq 16~

3. (30 puntos) ~N \leq 22~

4. (21 puntos) ~N \leq 28~

5. (19 puntos) ~N \leq 30~