batches yield containers of ammonia, so the minimum number of batches is . Producing more batches requires more raw material and cannot reduce the cost. It suffices to buy containers of nitrogen and containers of hydrogen, optimizing each purchase separately.
For either material, buy from the cheapest suppliers first. If an expensive supplier sells a container while a cheaper supplier still has unused stock, buy that container from the cheaper supplier instead. This keeps the quantity unchanged and reduces the cost. The order of suppliers with equal prices does not affect the cost. Sort the suppliers by price and buy the smaller of their stock and the remaining demand from each supplier. If the available stock of either material falls short, print -1.
With , the time complexity is and space complexity is . We buy containers, each costing at most , so the maximum feasible answer is .
Solution written by GPT