2026-09-09-21-04

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

class Program
{
    struct ItemInfoDef
    {
        internal long PriceHigh;
        internal long PriceLow;
    }

    static void Main()
    {
        var mItemInfoList = new List<ItemInfoDef>();

        Action<long, long> AddAct = (pHigh, pLow) =>
        {
            mItemInfoList.Add(new ItemInfoDef() { PriceHigh = pHigh, PriceLow = pLow });
        };

        //mItemInfoList.Clear();
        //AddAct(11, 6);
        //AddAct(6, 5);
        //AddAct(2, 1);
        //AddAct(8, 3);
        //AddAct(7, 4);
        //Console.WriteLine(SolveDFS(mItemInfoList));

        //mItemInfoList.Clear();
        //AddAct(5, 1);
        //AddAct(5, 2);
        //AddAct(5, 3);
        //AddAct(5, 4);
        //Console.WriteLine(SolveDFS(mItemInfoList));

        mItemInfoList.Clear();
        AddAct(24, 13);
        AddAct(24, 2);
        AddAct(50, 12);
        AddAct(35, 25);
        AddAct(28, 26);
        AddAct(10, 1);
        Console.WriteLine(SolveDFS(mItemInfoList));
    }

    static long SolveDFS(List<ItemInfoDef> pItemInfoList)
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CostSum = 0;
        WillPush.CouponCnt = 0;
        WillPush.ItemBitSet = 0;
        Stk.Push(WillPush);

        int AllBitOn = (1 << pItemInfoList.Count) - 1;

        long Answer = pItemInfoList.Sum(pX => pX.PriceHigh);
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            // クリア判定
            if (Popped.ItemBitSet == AllBitOn) {
                Answer = Math.Min(Answer, Popped.CostSum);
                continue;
            }

            if (Popped.CostSum >= Answer) continue;

            for (int I = 0; I <= pItemInfoList.Count - 1; I++) {
                int CurrBit = (1 << I);

                // クーポンを使用する場合
                if (Popped.CouponCnt > 0) {
                    if ((Popped.ItemBitSet & CurrBit) == 0) {
                        WillPush.CostSum = Popped.CostSum + pItemInfoList[I].PriceLow;
                        WillPush.CouponCnt = Popped.CouponCnt - 1;
                        WillPush.ItemBitSet = Popped.ItemBitSet | CurrBit;
                        Stk.Push(WillPush);
                    }
                }

                // クーポンを使用しない場合
                WillPush.CostSum = Popped.CostSum + pItemInfoList[I].PriceHigh;
                WillPush.CouponCnt = Popped.CouponCnt + 1;
                WillPush.ItemBitSet = Popped.ItemBitSet | CurrBit;
                Stk.Push(WillPush);
            }
        }
        return Answer;
    }

    struct JyoutaiDef
    {
        internal long CostSum;
        internal long CouponCnt;
        internal int ItemBitSet;
    }
}