euler 82

const {readFileSync} = require("fs");
const arr = readFileSync("82.txt", "utf8").split("\n").map(x => x.split(",").map(x => parseInt(x)));
const dp = Array(80).fill(0).map(() => Array(80).fill(0));
for (let i = 0; i < 80; i++) dp[i][0] = arr[i][0];
let ans = Infinity;
for (let i = 1; i < 80; i++) {
    for (let j = 0; j < 80; j++) {
        dp[j][i] = dp[j][i - 1];
        let x = 0;
        for (let k = j - 1; k >= 0; k--) {
            x += arr[k][i];
            dp[j][i] = Math.min(dp[j][i], x + dp[k][i - 1]);
        }
        x = 0;
        for (let k = j + 1; k < 80; k++) {
            x += arr[k][i];
            dp[j][i] = Math.min(dp[j][i], x + dp[k][i - 1]);
        }
        dp[j][i] += arr[j][i];
        if (i == 79) ans = Math.min(ans, dp[j][i]);
    }
}
console.log(ans);