## Editorial for Tưới nước đồng cỏ

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

uses math;
const fi='';
oo=1000000000;
var m,n,re:longint;
free:array[1..300] of boolean;
d,b:array[1..300] of longint;
a:array[1..300,1..300] of longint;

procedure rf;
var i,j:longint;
begin
for i:=1 to n do read(b[i]);
for i:=1 to n do
for j:=1 to n do read(a[i,j]);
end;

procedure pr;
var i,j,x,mn:longint;
begin
for i:=1 to n do
begin
free[i]:=true; d[i]:=b[i];
end;
mn:=maxlongint;
for i:=1 to n do
if b[i]<mn then
begin
mn:=b[i]; x:=i;
end;
free[x]:=false; re:=d[x];
for i:=1 to n-1 do
begin
for j:=1 to n do
if free[j] then
d[j]:=min(d[j],a[x,j]);
mn:=oo;
for j:=1 to n do
if free[j] and (mn>d[j]) then
begin
mn:=d[j]; x:=j;
end;
free[x]:=false; re:=re+d[x];
end;
writeln(re);
end;

begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.


#### Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 305

int c[N][N], n, d[N];
bool Free[N];

void enter() {
scanf( "%d", &n );
fo(i,1,n) {
scanf ( "%d", &c[0][i] );
c[i][0] = c[0][i];
}
fo(i,1,n) {
fo(j,1,n) scanf( "%d", &c[i][j] );
c[i][i] = INF;
}
}

int prim() {
fill(Free, Free+n+1, 1);
fill(d,d+n+1,INF); d[0] = 0;
int res = 0;
rep(k, n+1) {
int u, dmin = INF;
rep(i,n+1) if( Free[i] && d[i] < dmin ) {
dmin = d[i]; u = i;
}
res += d[u]; Free[u] = 0;
rep(v,n+1) if( Free[v] && d[v] > c[u][v] ) d[v] = c[u][v];
}
return res;
}

int main() {
//freopen( "input.txt", "r", stdin );
//freopen( "output.txt", "w", stdout );
enter();
printf( "%d\n", prim() );
return 0;
}


{$MODE OBJFPC} program fwater; uses math; type edge=record x,y,w:longint; end; const fi=''; maxn=303; maxm=10*maxn*maxn; var e:array[1..maxm] of edge; lab:array[1..maxn] of longint; res,n,m:longint; procedure input; var inp:text; i,j,c:longint; begin assign(inp,fi);reset(inp); readln(inp,n); for i:=1 to n do begin readln(inp,c); inc(m); e[m].x:=n+1; e[m].y:=i; e[m].w:=c; end; for i:=1 to n do begin for j:=1 to n do begin read(inp,c); if i=j then continue; inc(m); e[m].x:=i; e[m].y:=j; e[m].w:=c; end; readln(inp); end; close(inp); end; procedure sort(l,r:longint); var i,j:longint; p,t:edge; begin if l>=r then exit; i:=l;j:=r; p:=e[random(r-l+1)+l]; repeat while e[i].w<p.w do inc(i); while e[j].w>p.w do dec(j); if i<=j then begin if i<j then begin t:=e[i]; e[i]:=e[j]; e[j]:=t; end; inc(i); dec(J); end; until i>j; sort(l,j);sort(i,r); end; function root(u:longint):longint; begin if lab[u]<=0 then exit(u); result:=root(lab[u]); lab[u]:=result; end; procedure union(p,q:longint); begin if lab[p]<lab[q] then lab[q]:=p else begin if lab[p]=lab[q] then dec(lab[q]); lab[p]:=q; end; end; procedure process; var i,k,p,q:longint; begin k:=0; sort(1,m); for i:=1 to m do begin p:=root(e[i].x); q:=root(e[i].y); if p<>q then begin inc(k); inc(res,e[i].w); union(p,q); end; if k=n then exit; end; end; begin input; process; write(res); end.  #### Code mẫu của RR {$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=300;
var
n:longint;
kq:int64;
fin,d:array[1..MAXN] of longint;
c:array[1..MAXN,1..MAXN] of longint;
procedure inp;
var
f:text;
i,j:longint;
begin
assign(f,FINP); reset(f);
for i:=1 to n do read(f,d[i]);
for i:=1 to n do
for j:=1 to n do
close(f);
end;
procedure ans;
var
f:text;
begin
assign(f,FOUT); rewrite(f);
writeln(f,kq);
close(f);
end;
procedure solve;
var
i,u,v,k:longint;
begin
kq:=0;
for k:=1 to n do
begin
u:=0;
for i:=1 to n do
if fin[i]=0 then
if (u=0) or (d[i]<d[u]) then u:=i;
fin[u]:=1; kq:=kq+d[u];
for v:=1 to n do
if fin[v]=0 then
d[v]:=min(d[v],c[u,v]);
end;
end;
begin
inp;
solve;
ans;
end.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#define maxn 302
#define oo 1000000000

int min(int a,int b)
{
if(a<b)
return a;
else return b;
}

int main()
{
//freopen("FWATER.in","r",stdin);
int n;
int a[maxn][maxn],flag[maxn],d[maxn];
scanf("%d",&n);
n++;a[1][1]=0;d[1]=0;flag[1]=1;
for(int i = 2;i<=n;i++)
{
flag[i]=0;
scanf("%d",&a[1][i]);
a[i][1] = a[1][i];
d[i] = a[1][i];
}
for(int i = 2;i<=n;i++)
for(int j = 2;j<=n;j++)
scanf("%d",&a[i][j]);
int KQ = 0;
while(true)
{
//printf("1");
int fl = 0,minn =oo;
for(int i=1;i<=n;i++)
{
if(flag[i]==0)
{
fl=1;
break;
}
}
if(fl==0)
break;
for(int i = 1;i<=n;i++)
if(flag[i]==0 && d[i]<minn)
{
fl = i;
minn = d[i];
}
KQ = KQ+d[fl];
for(int i = 1;i<=n;i++)
d[i] = min(d[i],a[i][fl]);
flag[fl]=1;
}
printf("%d",KQ);
//getch();
}


#### Code mẫu của ll931110

{\$MODE DELPHI}
Program FWATER;
Const
input  = '';
output = '';
maxn = 300;
maxc = 100000000;
Var
a: array[0..maxn,0..maxn] of integer;
d,trace: array[0..maxn] of integer;
free: array[0..maxn] of boolean;
w: array[1..maxn] of integer;
n: integer;

Procedure init;
Var
f: text;
i,j: integer;
Begin
Assign(f, input);
Reset(f);

For i:= 1 to n do
Begin
a[i,0]:= a[0,i];
End;

For i:= 1 to n do
For j:= 1 to n do read(f, a[i,j]);

Close(f);
End;

Procedure Prim;
Var
u,v,i,k,min: integer;
Begin
Fillchar(free, sizeof(free), true);

For i:= 1 to n do d[i]:= maxc;
d[0]:= 0;

For k:= 0 to n do
Begin
u:= -1;
min:= maxc;

For i:= 0 to n do
if free[i] and (d[i] < min) then
Begin
min:= d[i];
u:= i;
End;

free[u]:= false;
For v:= 0 to n do
if free[v] and (d[v] > a[u,v]) then
Begin
d[v]:= a[u,v];
trace[v]:= u;
End;
End;
End;

Procedure printresult;
Var
f: text;
i,res: integer;
Begin
Assign(f, output);
Rewrite(f);

res:= 0;
For i:= 1 to n do res:= res + a[trace[i],i];

Writeln(f, res);
Close(f);
End;

Begin
init;
Prim;
printresult;
End.


#### Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX   333
using namespace std;
struct edge {
int u,v,w;
edge(){}
edge(int _u,int _v,int _w) {
u=_u;v=_v;w=_w;
}
bool operator < (const edge &x) const {
if (w<x.w) return (true);
if (w>x.w) return (false);
return (u+v<x.u+x.v);
}
};
vector<edge> e;
int n;
int up[MAX];
scanf("%d",&n);
int i,j,v;
for (i=1;i<=n;i=i+1) {
scanf("%d",&v);
e.push_back(edge(0,i,v));
e.push_back(edge(i,0,v));
}
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1) {
scanf("%d",&v);
if (i!=j) e.push_back(edge(i,j,v));
}
for (i=0;i<=n;i=i+1) up[i]=-1;
sort(e.begin(),e.end());
}
int find(int x) {
if (up[x]<0) return (x);
up[x]=find(up[x]);
return (up[x]);
}
void join(int a,int b) {
int x=find(a);
int y=find(b);
if (x==y) return;
up[y]=x;
}
void kruskal(void) {
int i;
int c=0;
int s=0;
for (i=0;i<e.size();i=i+1) {
if (find(e[i].u)!=find(e[i].v)) {
join(e[i].u,e[i].v);
s=s+e[i].w;
c=c+1;
if (c==n) {
printf("%d",s);
return;
}
}
}
}
int main(void) {
//freopen("tmp.inp","r",stdin);
kruskal();
return 0;
}


#### Code mẫu của khuc_tuan

import gc
gc.disable()
import sys
import psyco
psyco.full()

def main():

n = input()
C = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(n):
C[i+1][0] = C[0][i+1] = input()

for i in range(1,n+1):
T = [int(s) for s in raw_input().split()]
for j in range(1,n+1):
C[i][j] = T[j-1]

inT = [False for i in range(n+1)]
inT[0] = True
nearest = [i for i in C[0]]

total = 0

for kk in range(n):
min = 1000000000
imin = -1
for i in range(1,n+1):
if (not inT[i]) and (nearest[i]<min):
min = nearest[i]
imin = i

total += min

assert not imin==-1

inT[imin] = True
for i in range(1,n+1):
if (not inT[i]) and (C[i][imin]<nearest[i]):
nearest[i] = C[i][imin]

print total

main()