009 - 重商主義

時間制限 1 秒 / メモリ制限 64 MB / 得点 400 / x 9 /


TLE
1sec
MLE
64MB
得点
400

この問題は部分点があります。

問題

資本家を否定しようと思うものは、資本家たちの貨幣を破壊しなければならない。
── ウラジーミル・イリイチ・レーニン

3種類の相異なる金額のコインが∞枚あります。
それを使ってN円をちょうど払うとき、最小で何枚のコインが必要ですか。
求めてください。
ただし、どのようにしてもちょうど払えないときは-1を出力してください。

入力

money1 money2 money3
N

一行目に3種類のコインの金額が与えられます。
次に払う金額Nが与えられます。

出力

minCoin

制約と部分点

テストケースのうち点数の25%分は以下の制約を満たします。
$1$ ≤ $money$i ≤ $10$2
$1$ ≤ $N$ ≤ $10$2
テストケースのうち点数の75%分は以下の制約を満たします。
$1$ ≤ $money$i ≤ 5 * $10$3
$1$ ≤ $N$ ≤ 5 * $10$3

テストケース

例1

入力

1 2 3
1

出力

1

1円のコイン1枚でちょうど払えます。

例2

入力

1 2 3
7

出力

3

1円のコイン1枚と3円のコイン2枚
2円のコイン2枚と3円のコイン1枚
のどちらかで払うことができます。