2025-03-29-23-45

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

// https://atcoder.jp/contests/past202107-open/tasks/past202107_o
class Program
{
    static string InputPattern = "InputX";

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

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

    static void Main()
    {
        var TestData = new List<string>();
        TestData.Add("3");
        TestData.Add("7 1");
        TestData.Add("1 5");
        TestData.Add("5 8");
        long Res = Solve(TestData);
        Console.WriteLine(Res);
        return;

        var InsRandom = new Random();

        // 長さと値がランダムなListを作成
        for (int I = 1; I <= 3000; I++) {
            var RandList = new List<string>();
            int N = InsRandom.Next(1, 4);

            RandList.Add(N.ToString());
            for (int J = 1; J <= N; J++) {
                int Rand1 = InsRandom.Next(1, 10);
                int Rand2 = InsRandom.Next(1, 10);
                RandList.Add(string.Format("{0} {1}", Rand1, Rand2));
            }

            long Result1 = SolveNaive(RandList);
            long Result2 = Solve(RandList);

            if (Result1 != Result2) {
                Console.WriteLine("■■■差異あり■■■");

                Console.WriteLine("愚直={0},高速={1}", Result1, Result2);
                RandList.ForEach(pX => Console.WriteLine(pX));
            }
        }
    }

    // 愚直解
    static long SolveNaive(List<string> pInputList)
    {
        mNaiveABInfoList.Clear();

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

        foreach (string EachStr in pInputList.Skip(1)) {
            SplitAct(EachStr);
            NaiveABInfo WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mNaiveABInfoList.Add(WillAdd);
        }
        int UB = mNaiveABInfoList.Count - 1;
        var BSet = new HashSet<long>(mNaiveABInfoList.Select(pX => pX.B));

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrComputer = 0;
        WillPush.Money = 0;
        WillPush.CurrInd = 0;
        Stk.Push(WillPush);

        var AnswerList = new List<long>();

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();
            int CurrInd = Popped.CurrInd;

            // クリア判定
            if (Popped.CurrInd > UB) {
                AnswerList.Add(Popped.Money);
                continue;
            }

            long CurrMoney = Popped.Money + mNaiveABInfoList[CurrInd].A;

            if (Popped.CurrComputer >= mNaiveABInfoList[CurrInd].B) {
                WillPush.CurrComputer = Popped.CurrComputer;
                WillPush.Money = CurrMoney;
                WillPush.CurrInd = Popped.CurrInd + 1;
                Stk.Push(WillPush);
            }
            else {
                foreach (long EachB in BSet) {
                    if (mNaiveABInfoList[CurrInd].B <= EachB) {
                        WillPush.CurrComputer = EachB;
                        WillPush.Money = CurrMoney - EachB;
                        WillPush.CurrInd = Popped.CurrInd + 1;

                        if (WillPush.Money >= 0) {
                            Stk.Push(WillPush);
                        }
                    }
                }
            }
        }

        if (AnswerList.Count == 0) {
            return -1;
        }
        return AnswerList.Max();
    }

    struct NaiveABInfo
    {
        internal long A;
        internal long B;
    }
    static List<NaiveABInfo> mNaiveABInfoList = new List<NaiveABInfo>();

    struct JyoutaiDef
    {
        internal long CurrComputer;
        internal long Money;
        internal int CurrInd;
    }

    class ABInfoDef
    {
        internal bool IsMorning; // 朝か？
        internal long Val;
    }
    static List<ABInfoDef> mABInfoList1 = new List<ABInfoDef>();
    static List<ABInfoDef> mABInfoList2 = new List<ABInfoDef>();

    static long Solve(List<string> pInputList)
    {
        mABInfoList1.Clear();
        mABInfoList2.Clear();

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

        foreach (string EachStr in pInputList.Skip(1)) {
            SplitAct(EachStr);
            var WillAdd1 = new ABInfoDef();
            WillAdd1.IsMorning = true;
            WillAdd1.Val = wkArr[0];
            mABInfoList1.Add(WillAdd1);

            var WillAdd2 = new ABInfoDef();
            WillAdd2.IsMorning = false;
            WillAdd2.Val = wkArr[1];
            mABInfoList1.Add(WillAdd2);
        }

        // コンピュータの価値の累積Maxを更新したら、コンピュータを購入可能
        long RunMax = long.MinValue;
        for (int I = 0; I <= mABInfoList1.Count - 1; I++) {
            if (mABInfoList1[I].IsMorning) {
                mABInfoList2.Add(mABInfoList1[I]);
                continue;
            }

            if (RunMax < mABInfoList1[I].Val) {
                RunMax = mABInfoList1[I].Val;
                mABInfoList2.Add(mABInfoList1[I]);
            }
        }

        // 連続したMはまとめる
        for (int I = mABInfoList2.Count - 1; 0 <= I; I--) {
            if (I > 0) {
                if (mABInfoList2[I].IsMorning && mABInfoList2[I - 1].IsMorning) {
                    mABInfoList2[I - 1].Val += mABInfoList2[I].Val;
                    mABInfoList2.RemoveAt(I);
                }
            }
        }

        foreach (ABInfoDef EachABInfo in mABInfoList2) {
            Console.WriteLine("IsMorning={0},Val={1}", EachABInfo.IsMorning, EachABInfo.Val);
        }

        // 稼いだ金額の累積和
        long[] RunSum = new long[mABInfoList2.Count];
        for (int I = 0; I <= mABInfoList2.Count - 1; I++) {
            if (mABInfoList2[I].IsMorning) {
                RunSum[I] = mABInfoList2[I].Val;
            }
            else {
                RunSum[I] = 0;
            }

            if (I > 0) {
                RunSum[I] += RunSum[I - 1];
            }
        }

        // SegmentTreeクラス (RMQ and 1点更新)
        var InsSegmentTree = new SegmentTree(mABInfoList2.Count - 1, long.MaxValue);
        InsSegmentTree.Update(0, 0);

        for (int I = 0; I <= mABInfoList2.Count - 1; I++) {
            if (mABInfoList2[I].IsMorning) continue;

            int ResultInd = ExecNibunhou_LowerBound(mABInfoList2[I].Val, RunSum);
            Console.WriteLine("ResultInd={0}", ResultInd);
            if (ResultInd == -1 || ResultInd > I) {
                return -1;
            }

            long RangeMin = ResultInd;
            long RangeMax = I;
            if (RangeMin > 0) {
                RangeMin--;
            }

            long MinVal;
            long MinValInd;
            Console.WriteLine("セグ木のスキャン区間は[{0},{1}]", RangeMin, RangeMax);

            InsSegmentTree.GetMinInfo_Left(RangeMin, RangeMax, out MinVal, out MinValInd);
            if (MinVal == long.MaxValue) {
                return -1;
            }

            long Rest = RunSum[ResultInd] - MinVal;
            Console.WriteLine("Rest={0}", Rest);
            if (Rest < mABInfoList2[I].Val) {
                return -1;
            }
            long SetVal = MinVal + mABInfoList2[I].Val;

            Console.WriteLine("セグ木のInd{0}に{1}をセットします", I, SetVal);
            InsSegmentTree.Update(I, SetVal);
        }
        long AllASum = mABInfoList2.Where(pX => pX.IsMorning).Sum(pX => pX.Val);
        for (int I = mABInfoList2.Count - 1; 0 <= I; I--) {
            if (mABInfoList2[I].IsMorning == false) {
                long CurrVal = InsSegmentTree.Internal_Query(I, I);
                return AllASum - CurrVal;
            }
        }
        return -1;
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static int ExecNibunhou_LowerBound(long pVal, long[] pArr)
    {
        if (pArr.Length == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pArr.Last()) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pArr[0]) {
            return 0;
        }

        int L = 0;
        int R = pArr.GetUpperBound(0);

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pArr[Mid] >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }
}

#region SegmentTree
// SegmentTreeクラス (RMQ and 1点更新)
internal class SegmentTree
{
    private long[] mTreeNodeArr;
    private long UB; // 木のノードの配列のUB
    private long mLeafCnt; // 葉ノードの数
    private long mExternalArrUB;

    // 拡張機能 (最小値と、最小値を持つIndを返す)
    // 最小値が複数あったら、左側のIndを優先
    internal void GetMinInfo_Left(long pSearchStaInd, long pSearchEndInd,
        out long pMinVal, out long pMinValInd)
    {
        // 区間の最小値を求める
        pMinVal = Internal_Query(pSearchStaInd, pSearchEndInd);

        // 二分探索を行う
        long L = pSearchStaInd, R = pSearchEndInd;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;
            long LeftMin = Internal_Query(L, Mid);

            if (LeftMin == pMinVal) R = Mid;
            else L = Mid;
        }
        pMinValInd = ((Internal_Query(L, L) == pMinVal) ? L : R);
    }

    // 拡張機能 (最小値と、最小値を持つIndを返す)
    // 最小値が複数あったら、右側のIndを優先
    internal void GetMinInfo_Right(long pSearchStaInd, long pSearchEndInd,
        out long pMinVal, out long pMinValInd)
    {
        // 区間の最小値を求める
        pMinVal = Internal_Query(pSearchStaInd, pSearchEndInd);

        // 二分探索を行う
        long L = pSearchStaInd, R = pSearchEndInd;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;
            long RightMin = Internal_Query(Mid, R);

            if (RightMin == pMinVal) L = Mid;
            else R = Mid;
        }
        pMinValInd = ((Internal_Query(R, R) == pMinVal) ? R : L);
    }

    // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列
    private struct RangeInfoDef
    {
        internal long StaInd;
        internal long EndInd;
    }
    private RangeInfoDef[] mRangeInfo;

    // ノードのIndexの列挙を返す
    internal IEnumerable<long> GetNodeIndEnum()
    {
        for (long I = 0; I <= mExternalArrUB; I++) {
            yield return I;
        }
    }

    // 木のノードのUBを返す
    internal long GetUB()
    {
        return mExternalArrUB;
    }

    // コンストラクタ
    internal SegmentTree(long pExternalArrUB, long pInitVal)
    {
        mExternalArrUB = pExternalArrUB;

        // 簡単のため、葉ノード数を2のべき乗に
        long ArrLength = 0;
        for (long I = 1; I < long.MaxValue; I *= 2) {
            ArrLength += I;
            mLeafCnt = I;

            if (pExternalArrUB + 1 < mLeafCnt) break;
        }

        // すべての値をpInitValに
        UB = ArrLength - 1;
        mTreeNodeArr = new long[UB + 1];
        for (long I = 0; I <= UB; I++) {
            mTreeNodeArr[I] = pInitVal;
        }

        // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列の作成
        mRangeInfo = new RangeInfoDef[UB + 1];
        for (long I = 0; I <= UB; I++) {
            if (I == 0) {
                RangeInfoDef WillSet1;
                WillSet1.StaInd = 0;
                WillSet1.EndInd = mLeafCnt - 1;
                mRangeInfo[I] = WillSet1;
                continue;
            }
            long ParentNode = DeriveParentNode(I);
            RangeInfoDef ParentRangeInfo = mRangeInfo[ParentNode];

            RangeInfoDef WillSet2;
            long Mid = (ParentRangeInfo.StaInd + ParentRangeInfo.EndInd) / 2;

            if (I % 2 == 1) { // 奇数ノードの場合
                WillSet2.StaInd = ParentRangeInfo.StaInd;
                WillSet2.EndInd = Mid;
            }
            else { // 偶数ノードの場合
                WillSet2.StaInd = Mid + 1;
                WillSet2.EndInd = ParentRangeInfo.EndInd;
            }
            mRangeInfo[I] = WillSet2;
        }
    }

    // 親ノードの添字を取得
    private long DeriveParentNode(long pTarget)
    {
        return (pTarget - 1) / 2;
    }

    // 子ノードの添字(小さいほう)を取得
    private long DeriveChildNode(long pTarget)
    {
        return pTarget * 2 + 1;
    }

    // 葉ノードの配列の添字を木の添字に変換して返す
    private long DeriveTreeNode(long pLeafArrInd)
    {
        long BaseInd = UB - mLeafCnt + 1;
        return BaseInd + pLeafArrInd;
    }

    // 葉ノードの配列のK番目の値をNewValに変更
    internal void Update(long pK, long pNewVal)
    {
        long CurrNode = DeriveTreeNode(pK);
        mTreeNodeArr[CurrNode] = pNewVal;

        // 登りながら更新
        while (CurrNode > 0) {
            CurrNode = DeriveParentNode(CurrNode);
            long ChildNode1 = DeriveChildNode(CurrNode);
            long ChildNode2 = ChildNode1 + 1;
            mTreeNodeArr[CurrNode] =
                Math.Min(mTreeNodeArr[ChildNode1], mTreeNodeArr[ChildNode2]);
        }
    }

    // 開始添字と終了添字とカレントノードを引数として、最小値を返す
    internal long Internal_Query(long pSearchStaInd, long pSearchEndInd)
    {
        return Private_Query(pSearchStaInd, pSearchEndInd, 0);
    }
    private long Private_Query(long pSearchStaInd, long pSearchEndInd, long pCurrNode)
    {
        long CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
        long CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;

        // OverLapしてなければ、long.MaxValue
        if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)
            return long.MaxValue;

        // 完全に含んでいれば、このノードの値
        if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd)
            return mTreeNodeArr[pCurrNode];

        // そうでなければ、2つの子の最小値
        long ChildNode1 = DeriveChildNode(pCurrNode);
        long ChildNode2 = ChildNode1 + 1;

        long ChildVal1 = Private_Query(pSearchStaInd, pSearchEndInd, ChildNode1);
        long ChildVal2 = Private_Query(pSearchStaInd, pSearchEndInd, ChildNode2);
        return Math.Min(ChildVal1, ChildVal2);
    }

    internal void DebugPrint()
    {
        for (long I = 0; I <= UB; I++) {
            Console.WriteLine("mTreeNodeArr[{0}] = {1}", I, mTreeNodeArr[I]);
        }
    }
}
#endregion