A grocery store has a policy that when the cashiers give change back to the customers, they should use the fewest number of coins.1. Suppose that the store has infinite supplies of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent). Describe a greedy algorithm to make change using the fewest number of coins.2. If the store runs out of nickels (5 cents), then the greedy algorithm may not yield an optimal solution for some amounts of change. What is the smallest amount n in this case that the greedy algorithm fails to make change using the fewest number of coins?3. Suppose that the government adopts a different set of coin denominations, consisting of k denominations. Give an O(nk)-time dynamic-programming algorithm that makes change for any amount n using the fewest number of coins. This algorithm should work for any set of k coin denominations, as long as it includes a penny.