
class SimplexMethod:
    def __init__(self, restrictionNo:int, numOfVar:int, table:list):
        self.table = table
        self.numOfVar = numOfVar
        self.restrictionNo = restrictionNo
        self.optimalValuesSet = set()
        self.saveOriginalCostFunction = []
        self.certtificattTable = []
        self.optimalValues = []
        self.costList = []
        self.certificate = []
        self.cost = 0
        self.useAuxillarySimplex = False
        self.rowValues = ()
        self.colValues = ()
        self.answer = ()
    
    def setCost(self, value):
        self.cost = value

    def initializeMatrix(self):
        for i in range(self.numOfVar + self.restrictionNo - 1):
            vec: list = []
            for j in range(self.numOfVar + 1):
                vec.append(0)
            self.table.append(vec)

        for i in range(self.numOfVar):
            self.optimalValues.append(0)
            self.costList.append(0)

        for i in range(self.restrictionNo):
            vec:list = []
            for j in range(self.restrictionNo):
                vec.append(0)
            self.certtificattTable.append(vec)
            self.certificate.append(0)

    def fillCostList(self, i:int, value:int):
        self.costList[i] = value

    def fillRestrictionList(self, i:int, j:int, value:int):
        self.table[i][j] = value
        if i == 0:
            self.saveOriginalCostFunction.append(value)

    def verifyCanonicality(self):
        for j in range(len(self.table[0]) - self.restrictionNo - 1):
            countOnes = 0
            countZeros = 0
            value = (0, j)
            if self.table[0][j] == 0:
                for i in range(1,len(self.table)):
                    if self.table[i][j] == 1:
                        value = (i, j)
                        countOnes += 1
                    elif self.table[i][j] == 0: countZeros += 1
                if countZeros + countOnes == self.restrictionNo:
                    self.optimalValuesSet.add(value)
    
    def FormTableau(self):
        self.initializeMatrix()
        inputList = list(map(int, input().split()))
        for i in range(len(inputList)):
            self.fillCostList(i,int(inputList[i]))

        for i in range(self.restrictionNo):
            inputList2 = list(map(float, input().split()))
            if i == self.restrictionNo - 1: continue
            for j in range(len(inputList2)):
                self.fillRestrictionList(i, j,float(inputList2[j]))
        self.saveOriginalCostFunction.append(0)
        for i in range(self.restrictionNo):
            if i != 0:
                self.certtificattTable[i][i-1] = 1

    def FormAuxiliarySimplex(self):
        for i in range(self.numOfVar):
            self.table[self.restrictionNo + i - 1][i] = 1
            self.table[self.restrictionNo + i - 1][self.numOfVar] = self.costList[i]

        for i in range(self.numOfVar + 1):
            self.table[0][i] = 0

        for i in range(self.restrictionNo - 1):
            for  j in range(len(self.table[i])):
                self.table[0][j] -= self.table[i][j]
                if j < self.restrictionNo and i < self.restrictionNo:
                    self.certtificattTable[0][j] -= self.certtificattTable[i][j]
        self.setCost(self.table[0][self.numOfVar])

    def resetTable(self):
        # print(self.saveOriginalCostFunction)
        self.table[0] = self.saveOriginalCostFunction
        for i in range(len(self.certtificattTable[0])):
            self.certtificattTable[0][i] = 0
    
    def getPivotColumn(self):
        minCol = 0
        minValue = 101
        for j in range(self.numOfVar):
            if self.table[0][j] < 0:
                minCol = j
                minValue = self.table[0][j]
                break
        self.colValues = (minCol, minValue)
        return (minCol, minValue)

    def getPivotRow(self):
        pivRow = 0
        minPivotValue = 101
        for i in range(self.restrictionNo + self.numOfVar - 1):
            if self.table[i][self.colValues[0]] <= 0: continue
            else:
                value =  self.table[i][self.numOfVar]/self.table[i][self.colValues[0]]
                if value < minPivotValue:
                    minPivotValue = value
                    pivRow = i
        self.rowValues = (pivRow, minPivotValue)
        return (pivRow, minPivotValue)
    
    def makePivotRowOne(self):
        divValue = self.table[self.rowValues[0]][self.colValues[0]]
        for j in range(self.numOfVar):
            self.table[self.rowValues[0]][j] = self.table[self.rowValues[0]][j]/ divValue
        for i in range(self.restrictionNo):
            if self.rowValues[0] < self.restrictionNo - 1:
                self.certtificattTable[self.rowValues[0]][i] = self.certtificattTable[self.rowValues[0]][i]/divValue
        return self.table

    def getPivotSubtractionValues(self):
        values:list = []
        self.table = self.makePivotRowOne()
        for i in range(self.restrictionNo + self.numOfVar - 1):
            if i == self.rowValues[0]: 
                values.append(0)
            else:
                values.append(self.table[i][self.colValues[0]])
        return values

    def performNormalSimplex(self):
        subtractionValues = self.getPivotSubtractionValues()
        for i in range(self.restrictionNo + self.numOfVar -1):
            if i == self.rowValues[0]:
                continue
            for j in range(self.numOfVar + 1):
                if j < self.restrictionNo and i < self.restrictionNo - 1 and self.rowValues[0] < self.restrictionNo:
                    self.certtificattTable[i][j] = self.certtificattTable[i][j] - (self.certtificattTable[self.rowValues[0]][j] * subtractionValues[i])
                self.table[i][j] = self.table[i][j] - (self.table[self.rowValues[0]][j] * subtractionValues[i])
            self.optimalValuesSet.add((self.rowValues[0], self.colValues[0]))
        self.setCost(self.table[0][self.numOfVar])

    def optimalAnswer(self): 
        for value in self.optimalValuesSet:
            if value[1] < self.numOfVar and self.table[0][value[1]] == 0 and self.table[value[0]][value[1]] == 1:
                self.optimalValues[value[1]] = self.table[value[0]][self.numOfVar]
        self.certificate[0] = 1
        self.answer = (self.cost, self.optimalValues, self.certificate)

    def simplex(self):
        self.FormTableau()
        self.FormAuxiliarySimplex()
        while True:
            pivotCol = self.getPivotColumn()
            pivotRow = self.getPivotRow()
            if pivotRow[0] < self.restrictionNo - 1:
                if self.table[pivotRow[0]][self.numOfVar] != 0:
                    self.certificate[pivotRow[0]] = 1
            if pivotCol[1] > 0:
                self.resetTable()
                while True:
                    pivotCol = self.getPivotColumn()
                    pivotRow = self.getPivotRow()
                    if pivotRow[0] < self.restrictionNo - 1:
                        self.certificate[pivotRow[0]] = 1
                    if pivotCol[1] > 0:
                        self.optimalAnswer()
                        return  
                    self.performNormalSimplex()
            self.performNormalSimplex()

    def run(self):
        self.simplex()
        return self.answer