Yu-kun Likes an Integer

Time Limit : 3 sec, Memory Limit : 262144 KB

Problem A: Yu-kun Likes an Integer

Background

会津大学付属幼稚園はプログラミングが大好きな子供が集まる幼稚園である。園児の一人であるゆう君は、プログラミングと同じくらい数字が大好きだ。そんなゆう君は最近、表に0から9までのいずれかの数字の書かかれたプレートをn枚購入してn桁の数を作る遊びに熱中している。 今月もゆう君は貰ったお小遣いでn枚のプレートを買いに行こうと考えていた。

Problem

プレートは表に書かれている数字によって値段が異なる。 それらを使って作れるn桁の数をできる限り小さくしたい。 ゆう君の所持金額と各プレートの値段、購入するプレートの枚数が与えられるので、そこから作ることのできる数の最小値を求めよ。

購入するプレートの値段の総和が所持金額を超えなければ自由にプレートを購入できる。 同じ数字の書かれたプレートを複数枚購入しても良い。

プレートは必ずn枚購入しなければならない。n枚購入できない場合は "NA" と出力すること。

購入後はn枚のプレートを任意の順番で一直線上に並べる。 そうしてできる数字の列を10進数の数とし、その値が最小になるようにしたい。 先頭に1つ以上の0が連続していても良い。 ( 例えば 0019 なら 19 となり, 0000 なら 0 として考える )

図1は0、1、9のプレートを購入した場合についての説明である。

figure1
図1 : 0,1,9のプレートを購入した場合

Hint

この問題を解くに当たって、以下のことを参考にしても良い。 整数値を文字列に変換する方法を示す。 value を文字列として str に代入する。

Cの場合

#include<stdio.h>

int main(){
  int value = 123; // この値を文字列に変換する
  char str[6];     // この変数に value を文字列にしたものが入る
  sprintf(str,"%d",value);
  return 0;
}

C++の場合

#include<sstream>

using namespace std;

int main(){
  int value = 123; // この値を文字列に変換する
  string str;      // この変数に value を文字列にしたものが入る
  stringstream ss;
  ss << value;
  ss >> str;
  return 0;
}

JAVAの場合

class Main {
    public static void main(String args[]){
        int value = 123;           // この値を文字列に変換する
        String str = new Integer(value).toString(); // この変数に value を文字列にしたものが入る
    }
}

Input

n m
c0 c1 c2 ... c9

1行目に2つの整数 n ,m が空白区切りで与えられる。n は購入するプレートの枚数, m はゆう君の所持金額を表す。

2行目には10個の整数が空白区切りで与えられる。 ci ( i は0以上9以下 ) は表に i が書かれたプレートの値段を表す。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ n ≤ 5
  • 0 ≤ m ≤ 500
  • 1 ≤ ci ≤ 1000 ( 0 ≤ i ≤ 9 )

Output

n枚のプレートを購入し、それらを任意の順番で並べることでできる数の値の最小値を出力せよ。

先頭にいくつかの0を含む場合はそのまま出力すること。 ( 例えば答えが 0019 の場合は先頭の0を取り除いて 19 とするのではなく、そのまま 0019 と出力すること ) 所持金額では n 枚プレートを購入できない場合は "NA" と出力すること。

Sample Input 1

1 10
1 2 3 4 5 6 7 8 9 10

Sample Output 1

0

Sample Input 2

3 10
8 4 5 3 5 6 9 10 11 2

Sample Output 2

119

Sample Input 3

5 30
25 51 32 9 2 1 10 2 5 10

Sample Output 3

04555

Sample Input 4

5 100
101 101 101 101 101 101 101 101 101 101

Sample Output 4

NA