printf <- function(...) cat(sprintf(...))
 
solve <- function(v, S)
{
    printf("入力\n")
    printf("硬貨: [%s]\n", toString(v))
    printf("金額: %d\n\n", S)
 
    m <- max(v)
    N <- rep(Inf, 4 * m)
    N[v] <- 1
    c <- 0
 
    for (i in 1:S) {
        if (i > m) {
            c <- ifelse(N[i] == N[i - m] + 1, c + 1, 0)
            if (c == m) break
        }
 
        if (i + m > length(N)) N <- c(N, rep(Inf, 4 * m))
 
        if (N[i] != Inf) N[i + v] <- pmin(N[i + v], N[i] + 1)
    }
 
    q <- ifelse(c == m, (S - i) %/% m + 1, 0)
    n <- N[S - q * m]
    printf("出力\n")
    printf("使用枚数: %d\n\n\n", ifelse(n == Inf, -1, n + q))
}
 
V <- list(c(1, 7, 10), c(3, 7, 10), c(10, 19, 23, 47, 101))
 
for (v in V) solve(v, 123456789)

cHJpbnRmIDwtIGZ1bmN0aW9uKC4uLikgY2F0KHNwcmludGYoLi4uKSkKCnNvbHZlIDwtIGZ1bmN0aW9uKHYsIFMpCnsKICAgIHByaW50Zigi5YWl5YqbXG4iKQogICAgcHJpbnRmKCLnoazosqg6IFslc11cbiIsIHRvU3RyaW5nKHYpKQogICAgcHJpbnRmKCLph5HpoY06ICVkXG5cbiIsIFMpCgogICAgbSA8LSBtYXgodikKICAgIE4gPC0gcmVwKEluZiwgNCAqIG0pCiAgICBOW3ZdIDwtIDEKICAgIGMgPC0gMAoKICAgIGZvciAoaSBpbiAxOlMpIHsKICAgICAgICBpZiAoaSA+IG0pIHsKICAgICAgICAgICAgYyA8LSBpZmVsc2UoTltpXSA9PSBOW2kgLSBtXSArIDEsIGMgKyAxLCAwKQogICAgICAgICAgICBpZiAoYyA9PSBtKSBicmVhawogICAgICAgIH0KCiAgICAgICAgaWYgKGkgKyBtID4gbGVuZ3RoKE4pKSBOIDwtIGMoTiwgcmVwKEluZiwgNCAqIG0pKQoKICAgICAgICBpZiAoTltpXSAhPSBJbmYpIE5baSArIHZdIDwtIHBtaW4oTltpICsgdl0sIE5baV0gKyAxKQogICAgfQoKICAgIHEgPC0gaWZlbHNlKGMgPT0gbSwgKFMgLSBpKSAlLyUgbSArIDEsIDApCiAgICBuIDwtIE5bUyAtIHEgKiBtXQogICAgcHJpbnRmKCLlh7rliptcbiIpCiAgICBwcmludGYoIuS9v+eUqOaemuaVsDogJWRcblxuXG4iLCBpZmVsc2UobiA9PSBJbmYsIC0xLCBuICsgcSkpCn0KClYgPC0gbGlzdChjKDEsIDcsIDEwKSwgYygzLCA3LCAxMCksIGMoMTAsIDE5LCAyMywgNDcsIDEwMSkpCgpmb3IgKHYgaW4gVikgc29sdmUodiwgMTIzNDU2Nzg5KQ==