coins

from collections import namedtuple

Coordinates = namedtuple("Coordinates", ["x", "y"])

START_CHAR = "s"

class Cell:
    def __init__(self, value):
        self.value = int(value) if value != START_CHAR else value
        self.path = []

    def __repr__(self):
        return str(self.value)


def print_cell_field(cell_field):
    for row in cell_field:
        for elem in row:
            print(elem, end=" ")
        print()


def find_the_way(cell_field):
    print("finding da way...")
    start = None
    for i, row in enumerate(cell_field):
        for j, cell in enumerate(row):
            if cell.value == START_CHAR:
                print(f"start coords: {i}, {j}")
                start = Coordinates(i, j)
                cell_field[i][j].value = 0
    if start is None:
        print("no start point found!")
        raise Exception("No start point")

    print_cell_field(cell_field)
    for i in range(start.x, len(cell_field)):
        for j in range(start.y, len(cell_field[0])):
            print(f"i'm in ({i}, {j}) cell...")

            _cell = cell_field[i][j]
            _cell_left = cell_field[i][j - 1]
            _cell_above = cell_field[i - 1][j]

            _cell.path.append((i,j))
            if i == start.x and j == start.y:
                continue

            if i == start.x:
                _cell.value = _cell.value + _cell_left.value
                _cell.path.extend(_cell_left.path)
                continue

            if j == start.y:
                _cell.value = _cell.value + _cell_above.value
                _cell.path.extend(_cell_above.path)
                continue

            if _cell_above.value >= _cell_left.value:
                _cell.value = _cell.value + _cell_above.value
                _cell.path.extend(_cell_above.path)
            else:
                _cell.value = _cell.value + _cell_left.value
                _cell.path.extend(_cell_left.path)
    return cell_field[len(cell_field) - 1][len(cell_field[0]) - 1]


def main():
    # size_input_string = input("enter the size of cell_field (n, m): ")
    size_input_string = input()
    n, m = size_input_string.split()
    n = int(n)
    m = int(m)
    cell_field = []
    for i in range(n):
        row = []
        # row_input_string = input(f"enter row {i}: ")
        row_input_string = input()
        for cell_value in row_input_string.split():
            row.append(Cell(cell_value))
        cell_field.append(row)
    print_cell_field(cell_field)

    last_cell = find_the_way(cell_field)
    path =  list(reversed(last_cell.path))
    print(last_cell.value)
    print(path)


if __name__ == "__main__":
    main()