POH Lite 天才火消しエンジニア霧島 3.33秒

<?php
    // 入力をパース
    $input = file('php://stdin', FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);
        // 1行目は必要人数
        $ninzuu = (int)$input[0];
        // 2行目は会社数 使わない
        // $kaishasuu = (int)$input[1];
        // 3行目以降は人数+価格 最大50社しかない
        unset($input[0]);unset($input[1]);
        $list = array_map(function($a){
            // 0=>人数,1=>価格
            $t=explode(' ', $a, 2);
            return [(int)$t[0],(int)$t[1]];
        }, $input);

    // 動的計画法
    $data = [0=>0];
    foreach($list as $key1=>$val1){
        // 1社で越えている場合は0にだけ足せばいい
        if($val1[0]>=$ninzuu){
            if(isset($data[$val1[0]])){
                $data[$val1[0]] = min($data[$val1[0]], $val1[1]);
            }else{
                $data[$val1[0]] = $val1[1];
            }
            continue;
        }

        foreach($data as $key2=>$val2){
            // 既に人数を越えている場合は計算不要
            if($key2 >= $ninzuu){ continue; }

            // 対象人数の金額を登録
            $num = $key2+$val1[0];
            if(isset($data[$num])){
                // 既に値がある場合は安い方
                $data[$num] = min($data[$num], $val2+$val1[1]);
            }else{
                $data[$num] = $val2+$val1[1];
            }
        }
    }

    // 最低人数越えのキーのうち、最低金額のものを選択
    $minTotal = 250000000;
    foreach($data as $key=>$val){
        if($key >= $ninzuu && $val < $minTotal ){
            $minTotal = $val;
        }
    }
    print($minTotal . PHP_EOL);