Const
infile = 'rqnoj30.in';
outfile = 'rqnoj30.out';
Type
Rec = Record
l, r, p: Integer;
End;
Var
Data: Array[0..1000, 0..100] Of Longint;
tree: Array[0..1000] Of Rec;
map: Array[0..1000, 0..1000] Of Boolean;
map0: Array[0..1000] Of Integer;
a, b, i, j, m, n, t: Integer;
Procedure try(i, j: Integer);
Var
k: Integer;
Begin
Data[i, j] := 0;
If j = 0 Then Exit;
If (tree[i].l = 0) And (tree[i].r = 0) Then Begin
If tree[i].p > 0 Then Data[i, j] := tree[i].p;
Exit;
End;
If (tree[i].l <> 0) And (tree[i].r = 0) Then Begin
If Data[tree[i].l, j - 1] = -1 Then try(tree[i].l, j - 1);
If tree[i].p > 0 Then Data[i, j] := Data[tree[i].l, j - 1] + tree[i].p Else Data[i, j] := Data[tree[i].l, j - 1];
Exit;
End;
If (tree[i].l = 0) And (tree[i].r <> 0) Then Begin
If Data[tree[i].r, j - 1] = -1 Then try(tree[i].r, j - 1);
If tree[i].p > 0 Then Data[i, j] := Data[tree[i].r, j - 1] + tree[i].p Else Data[i, j] := Data[tree[i].r, j - 1];
If Data[tree[i].r, j] = -1 Then try(tree[i].r, j);
If Data[i, j] < Data[tree[i].r, j] Then Data[i, j] := Data[tree[i].r, j];
Exit;
End;
For k:=1 To j Do Begin
If Data[tree[i].l, k - 1] = -1 Then try(tree[i].l, k - 1);
If Data[tree[i].r, j - k] = -1 Then try(tree[i].r, j - k);
If tree[i].p > 0 Then Begin
If Data[i, j] < Data[tree[i].l, k - 1] + Data[tree[i].r, j - k] + tree[i].p Then Data[i, j] := Data[tree[i].l, k - 1] + Data[tree[i].r, j - k] + tree[i].p;
End Else Begin
If Data[i, j] < Data[tree[i].l, k - 1] + Data[tree[i].r, j - k] Then Data[i, j] := Data[tree[i].l, k - 1] + Data[tree[i].r, j - k];
End;
If Data[tree[i].r, j - k + 1] = -1 Then try(tree[i].r, j - k + 1);
If Data[i, j] < Data[tree[i].r, j - k + 1] Then Data[i, j] := Data[tree[i].r, j - k + 1];
End;
If Data[i, j] < 0 Then Data[i, j] := 0;
End;
Begin
Assign(input, infile);
Reset(input);
ReadLn(n, m);
For i:=1 To n Do Read(tree[i].p);
ReadLn;
FillChar(map, sizeof(map), False);
For i:=1 To n Do Begin
ReadLn(a, b);
If a > b Then Begin
t := a;
a := b;
b := t;
End;
map[a, b] := True;
End;
Close(input);
For i:=0 To n-1 Do
For j:=i+1 To n Do
If map[i, j] Then
If map0[i] = 0 Then Begin
tree[i].l := j;
map0[i] := j;
End Else Begin
tree[map0[i]].r := j;
map0[i] := j;
End;
FillChar(Data, sizeof(Data), $ff);
try(1, m);
Assign(output, outfile);
Rewrite(output);
WriteLn(Data[1, m]);
Close(output);
End.