change money

#include <stdio.h>
#include <string.h>
#define inf 0x23333333
#define N 100005

int n, s, r; // n 种面值, 目标 s, 剩下 r 元找不开
int v[N];    // 面值
int dp[N];   // 记忆 d(s)

int d(int s) {
    if (s < 0) return inf;
    if (dp[s] != inf) return dp[s];
    if (r > s) r = s;
    int result = inf;
    for (int i = 0; i < n; ++i)
        if (result > d(s - v[i]) + 1)
            result = d(s - v[i]) + 1;
    if (result != inf) dp[s] = result;
    return result;
}

int main() {
    scanf("%d%d", &n, &s);
    for (int i = 0; i < n; ++i) scanf("%d", &v[i]);
    dp[0] = 0; for (int i = 1; i <= s; ++i) dp[i] = inf; r = inf;
    if (d(s) == inf) printf("%d\n", d(s - r));
    else printf("%d\n", d(s));
}