2024-04-14-17-44

using System;
using System.Collections.Generic;
using System.Linq;

// ABC344-F Earn to Advance
// https://atcoder.jp/contests/abc344/tasks/abc344_f
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1 2 3");
            WillReturn.Add("3 1 2");
            WillReturn.Add("2 1 1");
            WillReturn.Add("1 2");
            WillReturn.Add("4 3");
            WillReturn.Add("4 2");
            WillReturn.Add("1 5 7");
            WillReturn.Add("5 3 3");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("1 1 1");
            WillReturn.Add("1 1 1");
            WillReturn.Add("1 1 1");
            WillReturn.Add("1000000000 1000000000");
            WillReturn.Add("1000000000 1000000000");
            WillReturn.Add("1000000000 1000000000");
            WillReturn.Add("1000000000 1000000000 1000000000");
            WillReturn.Add("1000000000 1000000000 1000000000");
            //4000000004
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int[,] mBanArr;
    static List<int[]> mYokoCostArrList = new List<int[]>();
    static List<int[]> mTateCostArrList = new List<int[]>();

    static int UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);
        UB = N - 1;

        mBanArr = CreateBanArr(InputList.Skip(1).Take(N));

        foreach (string EachStr in InputList.Skip(1 + N).Take(N)) {
            mYokoCostArrList.Add(EachStr.Split(' ').Select(pX => int.Parse(pX)).ToArray());
        }

        foreach (string EachStr in InputList.Skip(1 + N + N)) {
            mTateCostArrList.Add(EachStr.Split(' ').Select(pX => int.Parse(pX)).ToArray());
        }

        // 最小の行動回数[状態]なDP表
        var PrevDP = new Dictionary<string, long>();
        JyoutaiDef FirstJyoutai;
        FirstJyoutai.CurrX = 0;
        FirstJyoutai.CurrY = 0;
        FirstJyoutai.Money = 0;
        FirstJyoutai.MaxEran = mBanArr[0, 0];
        PrevDP[GetHash(FirstJyoutai)] = 0;

        var AnswerList = new List<long>();
        while (PrevDP.Count > 0) {
            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);

                long CurrX = CurrJyoutai.CurrX;
                long CurrY = CurrJyoutai.CurrY;

                Action<long, long> UpdateAct = (pNewX, pNewY) =>
                {
                    if (UB < pNewX || UB < pNewY) return;

                    long PayMoney = DerivePayMoney(CurrX, CurrY, pNewX, pNewY);
                    long NewMoney = CurrJyoutai.Money - PayMoney;
                    long NewVal = EachPair.Value + 1;

                    if (NewMoney < 0) {
                        long Div = Math.Abs(NewMoney) / CurrJyoutai.MaxEran;
                        if (Math.Abs(NewMoney) % CurrJyoutai.MaxEran > 0) {
                            Div++;
                        }
                        NewVal += Div;
                        NewMoney += CurrJyoutai.MaxEran * Div;
                    }

                    long NewMaxEran = Math.Max(CurrJyoutai.MaxEran, mBanArr[pNewX, pNewY]);

                    // クリア判定
                    if (pNewX == UB && pNewY == UB) {
                        AnswerList.Add(NewVal);
                        return;
                    }
                    JyoutaiDef NewJyoutai;
                    NewJyoutai.CurrX = pNewX;
                    NewJyoutai.CurrY = pNewY;
                    NewJyoutai.Money = NewMoney;
                    NewJyoutai.MaxEran = NewMaxEran;
                    string Hash = GetHash(NewJyoutai);
                    if (CurrDP.ContainsKey(Hash)) {
                        if (CurrDP[Hash] <= NewVal) {
                            return;
                        }
                    }
                    CurrDP[Hash] = NewVal;
                };

                UpdateAct(CurrX, CurrY + 1);
                UpdateAct(CurrX + 1, CurrY);
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(AnswerList.Min());
    }

    struct JyoutaiDef
    {
        internal long CurrX;
        internal long CurrY;
        internal long Money;   // 残金
        internal long MaxEran; // 最大日給
    }

    static JyoutaiDef GetJyoutai(string pHash)
    {
        string[] SplitArr = pHash.Split(',');
        JyoutaiDef WillReturn;
        WillReturn.CurrX = long.Parse(SplitArr[0]);
        WillReturn.CurrY = long.Parse(SplitArr[1]);
        WillReturn.Money = long.Parse(SplitArr[2]);
        WillReturn.MaxEran = long.Parse(SplitArr[3]);
        return WillReturn;
    }

    static string GetHash(JyoutaiDef pJyoutai)
    {
        return string.Format("{0},{1},{2},{3}",
            pJyoutai.CurrX, pJyoutai.CurrY, pJyoutai.Money, pJyoutai.MaxEran);
    }

    // 移動元座標と、移動先座標を引数として支払う金額を返す
    static long DerivePayMoney(long pFromX, long pFromY, long pToX, long pToY)
    {
        if (pFromX != pToX) {
            return mYokoCostArrList[(int)pFromY][pFromX];
        }
        else {
            return mTateCostArrList[(int)pFromY][pFromX];
        }
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static int[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new int[0, 0];
        }

        int[] IntArr = { };
        Action<string> SplitAct = pStr =>
            IntArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(StrList[0]);

        int UB_X = IntArr.GetUpperBound(0);
        int UB_Y = StrList.Count - 1;

        int[,] WillReturn = new int[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[Y]);
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }
}