Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

WWATER - Watering Hole

Paul Christiano, 2007
Points: 400

Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000). Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

Determine the minimum amount Farmer John will have to pay to water all of his pastures.

Input

  • Line 1: A single integer: N
  • Lines 2..N + 1: Line i+1 contains a single integer: W_i
  • Lines N+2..2N+1: Line N+1+i contains N space-separated integers; the j-th integer is P_ij

Output

  • Line 1: A single line with a single integer that is the minimum cost of providing all the pastures with water.

Example

Input:
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

Output:
9

Input details

There are four pastures. It costs 5 to build a well in pasture 1, 4 in pastures 2 and 3, 3 in pasture 4. Pipes cost 2, 3, and 4 depending on which pastures they connect.

Output details

Farmer John may build a well in the fourth pasture and connect each pasture to the first, which costs 3 + 2 + 2 + 2 = 9.


Adicionado por:Wanderley Guimarăes
Data:2008-10-24
Tempo limite:0.400s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Origem:USACO October 2008 Qualifying Round

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.