money.txt

/*
ID: achyuta2
LANG: JAVA
TASK: money
*/
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class money {
    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new FileReader("money.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("money.out")),true);
        StringTokenizer st = new StringTokenizer(f.readLine());
        int coinnum = Integer.parseInt(st.nextToken());
        int total = Integer.parseInt(st.nextToken());
        int[] coins = new int[coinnum];
        int counter =0;
        while (true){
            String x=f.readLine();
            if(x==null){
                break;
            }else{
                st = new StringTokenizer(x);
                while (st.hasMoreTokens()){
                    coins[counter]=Integer.parseInt(st.nextToken());
                    counter++;
                }
            }
        }
        Arrays.sort(coins);
        long[][] dp = new long[coinnum+1][total+1];
        for(int i=0; i<coinnum+1; i++){
            dp[i][0]=1;
        }
        for(int i=1; i<coinnum+1; i++) {
            for(int j=1; j<total+1; j++){
                dp[i][j]=dp[i-1][j];
                if(j-coins[i-1]>-1){
                    dp[i][j]=dp[i][j]+dp[i][j-coins[i-1]];
                }
            }
        }
        out.println(dp[coinnum][total]);
	out.close();
    }
}