piebuy.py

import heapq
import math

numTests = int(input())+1


def getminind(l):
    return heapq.nsmallest(1, ((k, i) for i, k in enumerate(l)))[0][1]


def updatemincosts(pies_bought, piecosts, upto):
    l = []
    for i in range(upto):
        pies_bought_on_day = pies_bought[i]
        l.append(piecosts[i][0] + 2*pies_bought_on_day + 1)
    return l

for testcase in range(1, numTests):
    n, m = [int(x) for x in input().split()]
    pies_bought = [0]*n
    total_cost = 0
    piecosts = []
    for each in range(n):
        piecosts.append(sorted([int(x) for x in input().split()]))
    mincosts = []
    i = 1
    for pie_n in range(1, n+1):
        mincosts = updatemincosts(pies_bought, piecosts, pie_n)
        minind = getminind(mincosts)
        piecosts[minind].pop(0)
        if piecosts[minind] == []:
            piecosts[minind].append(math.inf)
        pies_bought[minind] += 1
        total_cost += mincosts[minind]
    print("Case #%d: %d" % (testcase, total_cost))