The fewest coins from a limited supply

def min_coins_limited(coins, counts, amount):
    INF = float('inf')
    fewest = [0] + [INF] * amount
    for c, k in zip(coins, counts):
        size = 1
        while k > 0:
            b = min(size, k)                       # a bundle of b coins of value c
            for t in range(amount, b * c - 1, -1):  # 0/1: downwards
                fewest[t] = min(fewest[t], fewest[t - b * c] + b)
            k -= b
            size *= 2
    return -1 if fewest[amount] == INF else fewest[amount]

#include <algorithm>
#include <climits>
#include <vector>

int solve(const std::vector<int>& coins, const std::vector<int>& counts, int amount) {
    const int INF = INT_MAX / 2;
    std::vector<int> fewest(amount + 1, INF);
    fewest[0] = 0;
    for (size_t i = 0; i < coins.size(); ++i)
        for (int k = counts[i], size = 1; k > 0; size *= 2) {
            int b = std::min(size, k);
            long long w = (long long)b * coins[i];                 // one bundle
            for (long long t = amount; t >= w; --t) fewest[t] = std::min(fewest[t], fewest[t - w] + b);
            k -= b;
        }
    return fewest[amount] >= INF ? -1 : fewest[amount];
}

class Solution {
    public int minCoinsLimited(int[] coins, int[] counts, int amount) {
        final int INF = Integer.MAX_VALUE / 2;
        int[] fewest = new int[amount + 1];
        java.util.Arrays.fill(fewest, INF);
        fewest[0] = 0;
        for (int i = 0; i < coins.length; i++)
            for (int k = counts[i], size = 1; k > 0; size *= 2) {
                int b = Math.min(size, k);
                long w = (long) b * coins[i];                        // one bundle
                for (long t = amount; t >= w; t--) fewest[(int) t] = Math.min(fewest[(int) t], fewest[(int) (t - w)] + b);
                k -= b;
            }
        return fewest[amount] >= INF ? -1 : fewest[amount];
    }
}

function minCoinsLimited(coins, counts, amount) {
  const fewest = [0, ...new Array(amount).fill(Infinity)];
  for (let i = 0; i < coins.length; i++)
    for (let k = counts[i], size = 1; k > 0; size *= 2) {
      const b = Math.min(size, k), w = b * coins[i];         // one bundle
      for (let t = amount; t >= w; t--) fewest[t] = Math.min(fewest[t], fewest[t - w] + b);
      k -= b;
    }
  return fewest[amount] === Infinity ? -1 : fewest[amount];
}

fn solve(coins: &[i64], counts: &[i64], amount: i64) -> i64 {
    let n = amount as usize;
    let inf = i64::MAX / 2;
    let mut fewest = vec![inf; n + 1];
    fewest[0] = 0;
    for (i, &c) in coins.iter().enumerate() {
        let (mut k, mut size) = (counts[i], 1i64);
        while k > 0 {
            let b = size.min(k);
            let w = (b * c) as usize;                              // one bundle
            if w <= n {
                for t in (w..=n).rev() {
                    fewest[t] = fewest[t].min(fewest[t - w] + b);
                }
            }
            k -= b;
            size *= 2;
        }
    }
    if fewest[n] >= inf { -1 } else { fewest[n] }
}

import qualified Data.Map.Strict as M

solve :: [Int] -> [Int] -> Int -> Int
solve coins counts amount = maybe (-1) id (M.lookup amount (foldl add (M.singleton 0 0) bundles))
  where
    split k size | k <= 0 = [] | otherwise = let b = min size k in b : split (k - b) (2 * size)
    bundles = [(b * c, b) | (c, k) <- zip coins counts, b <- split k 1]
    -- a map from reachable total to the fewest coins; each bundle used at most once
    add best (w, b) = M.unionWith min best (M.fromList [(t + w, n + b) | (t, n) <- M.toList best, t + w <= amount])