El Granjero Juan (GJ) ha decidido llevar agua a sus ~N (1 <= N <= 300)~ pastizales, los cuales están numerados convenientemente ~1..N~. El puede llevar agua a un pastizal o construyendo un pozo en ese pastizal o conectando el pastizal a través de una tubería la cual ya tenga agua.

Taladrar un pozo en un pastizal ~i~ cuesta ~W_i (1 <= W_i <= 100,000)~. Conectar los pastizales ~i~ y ~j~ con una tuberia cuesta ~P_{ij} (1 <= P_{ij} <= 100,000; P_{ij}=P_{ji}; P_{ii}=0)~.

Determine la cantidad mínima que el Granjero Juan tiene que pagar para llevar agua a todos sus pastizales.

Entrada

• Línea 1: Un solo entero: ~N~
• Líneas 2..N + 1: La línea ~i+1~ contiene un solo entero: ~W_i~
• Líneas N+2:2N+1: La línea N+1+i contiene N enteros separados por espacios; el entero jésimo es ~P_{ij}~

Ejemplo de Entrada

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Detalles de la Entrada

Hay cuatro pastizales. Cuesta 5 construir un pozo en el pastizal ~1, 4~ en los pastizales ~2~ y ~3~, ~3~ en el pastizal ~4~. Las tuberías cuestan ~2, 3~, y ~4~ dependiendo que pastizales conectan.

Salida

Una sola línea con un solo entero que es el costo mínimo de llevar agua a todos los pastizales.

Ejemplo de Salida

9

Detalles de la Salida

El Granjero Juan puede construir un pozo en el cuarto pastizal y conectar cada pastizal al primero, lo que cuesta ~3 + 2 + 2 + 2 = 9~.