El Granjero Juan ha comprado una propiedad en el Caribe y va a tratar de introducir vacas lecheras en una granja grande compuesta de islas. Vistas las cosas de esa manera, él quiere rodear todas las islas con una cerca.

Cada isla en la granja tiene la forma de un polígono. El cerca las islas un lado al tiempo (entre un par de vértices consecutivos) y procede en sentido de las manecillas de un reloj alrededor de la isla dada con su operación de cerco. Como él quiere cercar todas las islas, él debe en algún tiempo viajar a otras islas usando un bote.

El puede comenzar a cercar en cualquier vértice y, en cual vértice donde él se encuentre, viajar a algún otro vértice en otra isla, cercarla, y luego volver de regreso al mismo vértice en la isla original usando el mismo camino que él había recorrido anteriormente. Cada viaje en bote tiene un costo definido por una matriz suministrada.

Las islas son descritas por un conjunto de ~N~ ~(3 \leq N \leq 500)~ pares de vértices ~V_1~, ~V_2~ ~(1 \leq V_1 \leq V_2 \leq N)~, por lo tanto usted debe darse cuenta como ensamblar esto en islas. Los vértices están convenientemente numerados ~1..N~.

¿Cuál es el costo mínimo de rodear las islas con la cerca?

Entrada

• Línea 1: Un solo entero ~N~.
• Líneas 2..N+1: Cada línea describe un borde de isla con dos enteros separados por espacios: ~V_1~ y ~V_2~
• Líneas N+2..2*N+1: La línea ~i-N-1~ contiene ~N~ enteros que describen la fila ~i~ de la matriz de costos: Fila_i.

Salida

Un solo entero que especifica el costo mínimo de construir el cerco.

Ejemplo de Entrada

12
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
0 15 9 20 25 8 10 13 17 8 8 7
15 0 9 12 10 10 8 15 15 8 8 9
9 12 0 25 20 18 16 14 13 7 12 12
20 12 25 0 8 13 14 15 15 10 10 10
25 10 20 8 0 16 20 18 17 18 9 11
8 10 18 13 16 0 10 9 11 10 8 12
10 8 16 14 20 10 0 18 20 6 16 15
13 15 14 15 18 9 18 0 5 12 12 13
17 15 13 15 17 11 20 5 0 22 8 10
8 8 7 10 18 10 6 12 22 0 11 12
8 8 12 10 9 8 16 12 8 11 0 9
7 9 12 10 11 12 15 13 10 12 9 0

Detalles de la Entrada:

  1        10            4
    xxxxxxx              x
   xxxxxxxxx            xxxx
7 xxxxxxxxxxx 6        xxxxxxx
  xxxxxxxxxxx       11 xxxxxxxxxx 5
   xxxxxxx
    xxx
  3         12 xxxxxxx 2
              xxxxxxxx
              xxxxxxxx
             xxxxxxxxx
             xxxxxxxxx
            xxxxxxxxxx
            xxxxxxxxxx
          8 xxxxxxxxxx 9

El ejemplo describe tres islas: {1,7,3,6,10}, {4,5,11} y {2,9,8,12}. Los costos están proporcionados como una matriz. Por ejemplo, el costo de ir del vértice ~1~ al vértice ~2~ es ~15~.

Ejemplo de Salida

30

Detalles de la Salida:

Hay más de una solución. Una es: GJ comienza en le vértice ~3~ luego va al ~7~ y para en ~1~, viaja al ~11~ seguido por ~4,5,11~. Luego se devuelve a ~1~, y viaja a ~12~ seguido por ~2,9,8,12~. Finalmente, él vuelve a ~1~ y continúa con ~10,6,3,7~. Los costos son ~8 * 2 = 16~ para viajar de ~1~ a ~11~ y volver, y ~7 * 2 = 14~ para ir de ~1~ a ~12~ y devolverse – un costo total de ~30~.