POH! Lite　C#模範解答

using System;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections;
using System.Diagnostics;
using System.Collections.Generic;

public class ClassName
{
    public static void Main()
    {
        int m = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        int sum_q = 0;
        int sum_r = 0;
        List<int[]> qr = new List<int[]>();
        for (int i = 0; i < n; i++)
        {
            string[] tmp = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            int q = int.Parse(tmp[0]);
            int r = int.Parse(tmp[1]);
            qr.Add(new int[] { q, r });
            sum_q += q;
            sum_r += r;
        }

        int dp_m = sum_q - m;
        int[] dp = new int[dp_m + 1];
        for (int i = 0; i < qr.Count; i++)
        {
            int q = qr[i][0];
            int r = qr[i][1];
            for (int j = dp.Length - 1; j >= q; j--)
            {
                dp[j] = Math.Max(dp[j], dp[j - q] + r);
            }
        }

        Console.WriteLine(sum_r - dp[dp_m]);
    }
}

using System;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections;
using System.Diagnostics;
using System.Collections.Generic;

public class ClassName
{
    public static void Main()
    {
        int m = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        List<int[]> qr = new List<int[]>();
        for (int i = 0; i < n; i++)
        {
            string line = Console.ReadLine();
            string[] tmp = line.Split(' ');
            qr.Add(new int[] { int.Parse(tmp[0]), int.Parse(tmp[1]) });
        }

        //m社のうちi番目の会社を使うか使わないかの表を作る
        //3社とかなら
        // A, B, C
        // 1, 1, 1
        // 1, 1, 0
        // 1, 0, 1
        //.....続く...
        //みたいな1を使う0は使わないの表を作る

        List<int[]> use_list = new List<int[]>();

        //2進数で考えると
        for (int i = 0; i < (1 << n); i++)
        {
            int[] array = new int[n];
            for (int j = 0; j < n; j++)
            {
                array[j] = (i >> j & 1);
            }
            use_list.Add(array);
        }

        //使う使わないリストから、人月を満たせる組み合わせで最安を探す
        int ans = 0;
        for (int i = 0; i < qr.Count; i++)
        {
            ans += qr[i][1];
        }
        for (int i = 0; i < use_list.Count; i++)
        {
            int cost = 0;
            int ningetsu = 0;
            for (int j = 0; j < use_list[i].Length; j++)
            {
                if (use_list[i][j] == 1)
                {
                    ningetsu += qr[j][0];
                    cost += qr[j][1];
                }
            }
            if (ningetsu >= m && ans > cost)
            {
                ans = cost;
            }
        }


        Console.WriteLine(ans);

    }
}