r,c = [int(x) for x in input().split() ]

nums = [ [int(x) for x in input().split()] for _ in range(r) ]

S = sum([sum(row) for row in nums])

if r%2 or c%2:
    print(S)
    exit()

skip = min( [ min(nums[i][i%2::2]) for i in range(r)] )

print(S-skip)

def max_lucky_clovers(r, c, grid):
    # Vytvoríme dva riadky pre dynamické programovanie
    prev_row = [0] * c
    curr_row = [0] * c

    # Inicializácia dolného ľavého rohu
    prev_row[0] = grid[r-1][0]

    # Naplnenie dynamickej tabuľky od dolného riadku smerom nahor
    for i in range(r-1, -1, -1):
        for j in range(c):
            # Ak sme v prvej bunke (dolný ľavý roh), už je inicializovaný
            if i == r-1 and j == 0:
                continue

            # Aktuálna hodnota je počet štvorlístkov na tomto políčku
            curr_row[j] = grid[i][j]

            # Pridáme maximum z predchádzajúcich ciest
            if i < r-1:  # Cesta zhora
                curr_row[j] += prev_row[j]
            if j > 0:  # Cesta zľava
                curr_row[j] = max(curr_row[j], grid[i][j] + curr_row[j-1])

        # Posunieme riadky na ďalšiu iteráciu
        prev_row, curr_row = curr_row, [0] * c

    # Výsledok je v pravom hornom rohu
    return prev_row[c-1]

# Vstupné spracovanie
r, c = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(r)]

# Výpočet maximálneho počtu štvorlístkov
print(max_lucky_clovers(r, c, grid) + 1)

def won(grid, k, c):
    
    dirs = ( (1,0), (0,1), (1,1), (1,-1) )

    n = len(grid)

    for x in range(n):
        for y in range(n):
            for d in dirs:
                dx, dy = d
                ok = True
                nx,ny = x,y

                for i in range(k):
                    if nx < 0 or ny < 0 or nx>=n or ny>=n or grid[nx][ny] != c:
                        ok = False
                        break
                    nx += dx
                    ny += dy

                if ok:
                    return True
    return False


def solve():
    n,k = [int(x) for x in input().split()]

    old = [ input() for _ in range(n) ]

    turned = [ ''.join([ old[n-1-i][k] for i in range(n) ]) for k in range(n)]

    grid = [ '' for _ in range(n) ]

    for c in range(n):
        for r in range(n):
            zeton = turned[n-1-r][c]
            if zeton != '.':
                grid[c] += zeton

    for i in range(n):
        grid[i] = grid[i] + '.' * (n-len(grid[i]))

    Erika = won(grid, k, 'R')
    Diabol = won(grid, k, 'B')

    print(['Nikto','Erika','Diabol','Dilema'][Erika+2*Diabol])


t = int(input())

for _ in range(t):
    solve()

def otoc_a_padni(siet):
    velkost = len(siet)
    otocena = [['.'] * velkost for _ in range(velkost)]

    # Otoèenie o 90° v smere hodinových ruèièiek
    for riadok in range(velkost):
        for stlpec in range(velkost):
            otocena[stlpec][velkost - 1 - riadok] = siet[riadok][stlpec]

    # Simulácia gravitácie
    for stlpec in range(velkost):
        stlpce_bez_bodiek = [otocena[riadok][stlpec] for riadok in range(velkost) if otocena[riadok][stlpec] != '.']
        for riadok in range(velkost):
            otocena[riadok][stlpec] = '.' if riadok < velkost - len(stlpce_bez_bodiek) else stlpce_bez_bodiek[
                riadok - (velkost - len(stlpce_bez_bodiek))]

    return otocena


def kontrola_vyhercu(siet, pocet_k):
    velkost = len(siet)

    def vyhra_znak(znak):
        for riadok in range(velkost):
            for stlpec in range(velkost):
                if stlpec <= velkost - pocet_k and all(
                        siet[riadok][stlpec + posun] == znak for posun in range(pocet_k)):
                    return True
                if riadok <= velkost - pocet_k and all(
                        siet[riadok + posun][stlpec] == znak for posun in range(pocet_k)):
                    return True
                if riadok <= velkost - pocet_k and stlpec <= velkost - pocet_k and all(
                        siet[riadok + posun][stlpec + posun] == znak for posun in range(pocet_k)):
                    return True
                if riadok <= velkost - pocet_k and stlpec >= pocet_k - 1 and all(
                        siet[riadok + posun][stlpec - posun] == znak for posun in range(pocet_k)):
                    return True
        return False

    vyhra_r = vyhra_znak('R')
    vyhra_b = vyhra_znak('B')

    if vyhra_r and vyhra_b:
        return "Dilema"
    elif vyhra_r:
        return "Erika"
    elif vyhra_b:
        return "Diabol"
    else:
        return "Nikto"


def riesenie_connect_k(zoznam_sieti):
    vysledky = []
    for siet in zoznam_sieti:
        velkost, pocet_k, hracia_plocha = siet
        otocena_plocha = otoc_a_padni(hracia_plocha)
        vysledok = kontrola_vyhercu(otocena_plocha, pocet_k)
        vysledky.append(vysledok)
    return vysledky


pocet_pripadov = int(input())
zoznam_sieti = []
for _ in range(pocet_pripadov):
    velkost, pocet_k = map(int, input().split())
    hracia_plocha = [input().strip() for _ in range(velkost)]
    zoznam_sieti.append((velkost, pocet_k, hracia_plocha))

vysledky = riesenie_connect_k(zoznam_sieti)
print("\n".join(vysledky))

def process_unicorns(tests):
    results = []
    for test in tests:
        kyslosti = sorted(set(test[1]))  # Najskôr zoradíme unikátne kyslosti vzostupne

        n = len(kyslosti)
        result = []
        for i in range(n // 2):
            result.append(kyslosti[-(i + 1)])  # Najkyslejšia
            result.append(kyslosti[i])  # Najmenej kyslá

        if n % 2 == 1:  # Ak je počet kyslostí nepárny, pridáme poslednú strednú hodnotu
            result.append(kyslosti[n // 2])

        results.append((len(result), result))

    return results


# Vstup
J = int(input())
tests = []

for _ in range(J):
    n = int(input())
    kyslosti = list(map(int, input().split()))
    tests.append((n, kyslosti))

# Spracovanie
results = process_unicorns(tests)

# Výstup
for res in results:
    print(res[0])
    print(" ".join(map(str, res[1])))