#include <iostream>
#include<climits>
using namespace std;
int N,M;
int r[5]; ///sorok ajanlata
int c[100001][5][5]; /// c[j][x][y] => j. oszlop ajanlata x, y kozott
void be()
{
    cin>>N>>M;
    for(int i=1;i<=N;i++) cin>>r[i];
    for(int j=1;j<=M;j++)
        for(int x=1;x<=N;x++)
            for(int y=x;y<=N;y++) cin>>c[j][x][y];
}
void megold()
{
    long long sum;
    long long mini=0;
    /// ha minden sor festve van
    for(int i=1;i<=N;i++) mini+=r[i];

    if(N==2) ///csak 2 sor van
    {
        /// nincs sor festve
        sum=0;
        for(int j=1;j<=M;j++)
        {
             sum+=min(c[j][1][1]+c[j][2][2],c[j][1][2]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 sor festve van
        sum=r[1];
        for(int j=1;j<=M;j++)
        {
             sum+=min(c[j][2][2],c[j][1][2]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2 sor festve van
        sum=r[2];
        for(int j=1;j<=M;j++)
        {
             sum+=min(c[j][1][1],c[j][1][2]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

    }
    else if(N==3) /// 3 sor van
    {
        /// nincs sor festve
        sum=0;
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(c[j][1][1]+c[j][2][2]+c[j][3][3],c[j][1][1]+c[j][2][3]),c[j][1][2]+c[j][3][3]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 sor festve van
        sum=r[1];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(c[j][2][2]+c[j][3][3],c[j][2][3]),c[j][1][2]+c[j][3][3]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2 sor festve van
        sum=r[2];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(c[j][1][1]+c[j][3][3],c[j][1][1]+c[j][2][3]),c[j][1][2]+c[j][3][3]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R3 sor festve van
        sum=r[3];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(c[j][1][1]+c[j][2][2],c[j][1][2]),c[j][1][1]+c[j][2][3]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 es R2 festve van, R3 nincs
        sum=r[1]+r[2];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(c[j][3][3],c[j][2][3]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 es R3 festve van, R2 nincs
        sum=r[1]+r[3];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(c[j][2][2],c[j][2][3]),c[j][1][2]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2 es R3 festve van, R1 nincs
        sum=r[2]+r[3];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(c[j][1][1],c[j][1][2]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig
    }
    else /// N==4 sor van
    {
        /// nincs sor festve
        sum=0;
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(min(min(min(c[j][1][1]+c[j][2][2]+c[j][3][3]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][3][3]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][1][1]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 sor festve van
        sum=r[1];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(min(min(min(c[j][2][2]+c[j][3][3]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][3][3]+c[j][4][4]),c[j][2][3]+c[j][4][4]),c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2 sor festve van
        sum=r[2];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(min(min(min(c[j][1][1]+c[j][3][3]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][3][3]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][1][1]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R3 sor festve van
        sum=r[3];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(min(min(min(c[j][1][1]+c[j][2][2]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][1][1]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R4 sor festve van
        sum=r[4];
        for(int j=1;j<=M;j++)
        {
              sum+=min(min(min(min(min(min(min(c[j][1][1]+c[j][2][2]+c[j][3][3],c[j][1][4]),
                c[j][1][2]+c[j][3][3]),c[j][1][1]+c[j][2][3]),c[j][1][1]+c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]), c[j][1][1]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R2 sor festve van
        sum=r[1]+r[2];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(c[j][3][3]+c[j][4][4],c[j][1][4]),
                c[j][2][3]+c[j][4][4]),c[j][3][4]),
                 c[j][1][3]+c[j][4][4]), c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R3 sor festve van
        sum=r[1]+r[3];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(min(min(c[j][2][2]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][4][4]),c[j][2][3]+c[j][4][4]),c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R4 sor festve van
        sum=r[1]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(min(min(c[j][2][2]+c[j][3][3],c[j][1][4]),
                c[j][1][2]+c[j][3][3]),c[j][2][3]),c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]), c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2+R3 sor festve van
        sum=r[2]+r[3];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(min(c[j][1][1]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][4][4]),c[j][1][1]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][1][1]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2+R4 sor festve van
        sum=r[2]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(min(min(c[j][1][1]+c[j][3][3],c[j][1][4]),
                c[j][1][2]+c[j][3][3]),c[j][1][1]+c[j][2][3]),c[j][1][1]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]), c[j][1][1]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig


        /// R3+R4 sor festve van
        sum=r[3]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(c[j][1][1]+c[j][2][2],c[j][1][4]),
                c[j][1][2]),c[j][1][1]+c[j][2][3]),
                 c[j][1][3]), c[j][1][1]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig


        /// R1+R2+R3 sor festve van
        sum=r[1]+r[2]+r[3];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(c[j][4][4],c[j][1][4]),
                c[j][3][4]),
                c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R2+R4 sor festve van
        sum=r[1]+r[2]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(c[j][3][3],c[j][1][4]),
                c[j][2][3]),c[j][3][4]),
                 c[j][1][3]),c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R3+R4 sor festve van
        sum=r[1]+r[3]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(c[j][2][2],c[j][1][4]),
                c[j][1][2]),c[j][2][3]),
                 c[j][1][3]), c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2+R3+R4 sor festve van
        sum=r[2]+r[3]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(c[j][1][1],c[j][1][4]),
                c[j][1][2]),
                 c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig
    }
    cout<<mini;
}
int main()
{
    be();
    megold();
    return 0;
}