N,M = map(int,input().split())
soronkent = list(map(int,input().split()))

matrix = []
for Oszlop in range(M):
    sor = list(map(int,input().split()))
    matrix.append(sor)

if N == 2:
    #Mindkét sor festve
    eset = [sum(soronkent)]
    #Csak első sor festve
    osszeg = soronkent[0]
    for Oszlop in range(M):
        osszeg += min([matrix[Oszlop][2],matrix[Oszlop][1]])
    eset.append(osszeg)
    #Csak második sor festve
    osszeg = soronkent[1]
    for Oszlop in range(M):
        osszeg += min([matrix[Oszlop][0],matrix[Oszlop][1]])
    eset.append(osszeg)
    #Nincs sor festve
    osszeg = 0
    for Oszlop in range(N):
        osszeg += min([matrix[Oszlop][0]+matrix[Oszlop][2],matrix[Oszlop][1]])
    eset.append(osszeg)
    print(min(eset))
if N == 3:
    #Minden sor festve
    eset = [sum(soronkent)]
    tools = [[0],[1],[2],[0,1],[0,2],[1,2],[]]
    check = [[0,3,5],[0,4],[1,5],[2],[1,4]]
    for sor in tools:
        lista = []
        osszeg = 0
        for x in sor:
            osszeg += soronkent[x]
        lista.append(osszeg)
        for Oszlop in range(M):
            valami = []
            for y in check:
                bennevan = False
                for z in sor:
                    if z in y:
                        bennevan = True
                if not bennevan:
                    seged = []
                    for j in y:
                        seged.append(matrix[Oszlop][j])
                    valami.append(sum(seged))
            lista.append(min(valami))
        eset.append(sum(lista))                                      
    print(min(eset))
if N == 4:
    eset = [sum(soronkent)]
    tools = [[0],[1],[2],[3],[0,1],[0,2],[0,3],[1,2],[1,3],[2,3],[0,1,2],[1,2,3],[0,2,3],[0,1,3],[]]
    check = [[0,4,7,9],[1,7,9],[0,5,9],[0,4,8],[1,8],[0,6],[2,9],[3],[1,6],[1,5,9],[2,8],[0,5,8],[2,6]]
    for sor in tools:
        lista = []
        osszeg = 0
        for x in sor:
            osszeg += soronkent[x]
        lista.append(osszeg)
        for Oszlop in range(M):
            valami = []
            for y in check:
                bennevan = False
                for z in sor:
                    if z in y:
                        bennevan = True
                if not bennevan:
                    seged = []
                    for j in y:
                        seged.append(matrix[Oszlop][j])
                    valami.append(sum(seged))
            lista.append(min(valami))
        eset.append(sum(lista))                                      
    print(min(eset))