15 10.11

private infix fun Boolean.arrow(other: Boolean) = !(this && !other)

private val invalid = 0 to 1e9.toInt() // max / min
private val invalid2 = Triple(0, 1e9.toInt(), listOf<Int>())

private fun dfs(
    tab: List<List<Int>>,
    n: Int = 0,
    m: Int,
    dp: List<MutableList<Triple<Int, Int, List<Int>>>> = List(tab.size) { MutableList(tab.first().size) { invalid2 } }.also { list ->
        (0..9).forEach { list[tab.size - 1][it] = Triple(tab[tab.size - 1][it], tab[tab.size - 1][it], listOf(it)) }
    }
): Triple<Int, Int, List<Int>> {
    if (n >= tab.size - 1 || m !in 0..9)
        return invalid2

    if (dp[n][m] != invalid2)
        return dp[n][m]

    dp[n][m] = run {
        val f = dfs(tab, n + 1, m - 1, dp)
        val s = dfs(tab, n + 1, m + 1, dp)
        val t = dfs(tab, n + 1, m, dp)
        arrayOf(f, s, t).minByOrNull { it.second }!!
    }.let { (f, s, t) ->
        val c = tab[n][m]
        Triple(f + c, s + c, t + m)
    }

    return dp[n][m]
}

fun main() {
    val list = (0..9).map { readLine()!!.trim().split("\t").map(String::toInt) }
    (0..9).map { dfs(list, m = it) }.minByOrNull { it.second }!!.let { (_, _, l) ->
        println("FIRST: ${list[list.size - 1][l.first()]} LAST: ${list[0][l.last()]}")
    }
}