No.247 線形計画問題もどき

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 121
作問者 : yuki2006yuki2006
12 ProblemId : 678 / 出題時の順位表

問題文

関数$\displaystyle f(x_1,x_2,\dots,x_N)=\sum_{i=1} ^N a_i x_i=a_1x_1+a_2x_2+\dots+a_Nx_N$ とする。
この時$f(x_1,x_2,\dots,x_N)=C$の制約下での $\displaystyle \sum_{i=1} ^N x_i$の最小値を求めてください。
ただし、$x_i$は非負の整数変数であり、$a_i$,$C$は自然数の定数であるとする。
この時、非負の整数解がなければ$-1$を出力してください。

入力

$C$
$N$ 
$a_1\ a_2\ \dots\ a_N$

入力は全て整数で与えられる。
$1 \le C \le \ 100000=10^5$
$1 \le N \le 100$
$1 \le a_i \le \ 100000=10^5$

出力

問題の制約下での $\displaystyle \sum_{i=1} ^N x_i$の最小値を求めてください。

サンプル

サンプル1
入力
10
3
3 2 1
出力
4

この時、関数$f$は$3x_1+2x_2+x_3 $である。$3x_1+2x_2+x_3=10 $の制約下での解の組は
$(x_1,x_2,x_3)=(0,1,8)$
$(x_1,x_2,x_3)=(0,0,10)$
$(x_1,x_2,x_3)=(0,2,6)$
$(x_1,x_2,x_3)=(1,2,3)$
$(x_1,x_2,x_3)=(3,0,1)$
$(x_1,x_2,x_3)=(0,5,0)$
など多数存在するが、
$\sum_{i=1} ^N x_i$の最小値は$(x_1,x_2,x_3)=(3,0,1)$ の時の$4$である。

サンプル2
入力
20
4
3 7 12 25
出力
4

$(x_1,x_2,x_3,x_4)=(2,2,0,0)$のとき $4$になる。

サンプル3
入力
100
3
90 9 12
出力
-1

$90x_1+9x_2+12x_3 =100$を満たす非負の整数の解は存在しないため $-1$を出力する。

サンプル4
入力
100
1
50 
出力
2

サンプル5
入力
100000
4
100000 50000 25000 12500
出力
1

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。