Monete minime: il greedy fallisce

Con monete da [1, 4, 6, 9], qual è il numero minimo di monete per fare 12? (il greedy dal più grande non è ottimo qui)