class Dynamic3 {

  public static int change(int amount, int[] coins){
    int k = coins[0]+1;
    int[] tab = new int[k];
     
    tab[0]=0;   
    for(int i = 1; i <= amount; i++) {
      tab[i%k] = Integer.MAX_VALUE;
      for(int j = coins.length-1; j >= 0 ; j--) { 
        if (i >= coins[j]){
          int c = 1 + tab[(i-coins[j])%k];
          if (c < tab[i%k]) tab[i%k] = c;
        }
      }
    } 
    return(tab[amount%k]);
  }
}