# Descripción

En una investigación en la Luna hay $N$ sensores diferentes(numerados de 0 a $N-1$) investigando $N$ cráteres(también numerados de 0 a $N-1$), cada sensor en un un crater diferente.

Para realizar la siguiente fase de experimentación, es necesario colocar el sensor 0 en el cráter 0, el sensor 1 en el cráter 1, etc. (en general, el sensor $i$ en el crater $i$ para todo entero $i$ entre 0 y $n-1$, inclusive).

Los sensores sólo pueden ser cambiados mediante un procedimiento que realiza un robot, el cual consiste en intercambiar el contenido de los cráteres $i$ y $k$, para lo cual requiere gastar $w(i, k)$ de energía (es decir, dependiendo de cuales dos cráteres intercambie el contenido, la cantidad de energía gastada será diferente).

Aunque el robot gaste diferentes cantidades de energía en cada intercambio; la acción de realizar un intercambio toma aproximadamente el mismo tiempo, sin importar cuales 2 cráteres estén involucrados en el intercambio.

El equipo quiere colocar los sensores en su lugar lo antes posible, por lo cual quiere encontrar la menor cantidad de intercambios para colocar los sensores en su lugar.

Además, le gustaría no gastar más de la energía necesaria para cumplir esta tarea; por lo cual, quiere encontrar la menor cantidad de energía necesaria para poner los sensores en su lugar en el menor tiempo posible (es decir, con la menor cantidad de intercambios).

# Entrada

Línea 1: $N$, el número de sensores

Línea 2: $N$ enteros separados por espacios, indicando qué sensor hay originalmente en cada cráter.

Siguientes $N$ líneas: una matriz indicando los costos $W$, de manera que el k-ésimo número de la i+3 - ésima línea indicará el costo de intercambiar el contenido de los cráteres i y k. La matriz será simétrica (es decir $W(i, k) = W(k,i)$ para toda entrada $(i, k)$ en la matriz)

# Salida

Línea 1: La mínima cantidad de intercambios

Línea 2: La mínima cantidad de energía para poner los sensores en su lugar haciendo el mínimo de intercambios.

# Ejemplo

||input
4
1 2 3 0
0 2 1 100
2 0 2 2
1 2 0 2
100 2 2 0
||output
3
5
||end

||input
4
1 2 0 3
0 10 10 1
10 0 10 1
10 10 0 1
1 1 1 0
||output
2
20
||end

**NOTA:** Como se muestra en el segundo ejemplo, si por algún motivo hay que elegir entre priorizar realizar menos intercambios o usar menos energía, lo preferible siempre es minimizar el número de intercambios.

# Límites

$3 \le N \le 100$

## Subproblema A (10 puntos)

* $3 \le N \le 10$

## Subproblema B (30 puntos)

* $11 \le N \le 19$
  * Para obtener los puntos de esta subtarea debes resolver la subtarea A.

## Subproblema C (60 puntos)

* $20 \le N \le 100$
  * Para obtener los puntos de esta subtarea debes resolver las subtareas A y B.