Souveniers

This problem gives us a set of rules about how individual merchants can make change based on what type of payment we use. The key insights are that we visit the merchants in order. Given that we visit them in a specific order, we have the choice to not buy goods, buy them with gold, or buy them with silver. If we evaluate this for all possible combinations of gold and silver, we can come up with an optimal solution.

DP state:

1. amount of gold coins (100)
2. amount of silver coins (10k)
3. which merchant we're on (100)

Store:

1. The max number of souvenirs bought

Evaluate:

1. Don't buy anything (same number of coins, and on the next merchant with same amount of souvenir)
2. Buy in gold (next merchant with appropriate number of gold and silver remaining and one more souvenir)
3. buy in silver (same as buy in gold, but do the math using silver)

Iterate over any amount of silver and gold after the last merchant and see which gives the most souvenir.

Runtime: 10^2 * 10^2 * 10^4 = 10^8 = fast enough