Informatica Online Judge

  Money Systems [0282 / 011A]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 84   Total Tried : 109


The Champion of this Problem (C++) : gs18021 - ms / 301byte
My Best Submission (C++) : N/A

[]

Background

일반적으로 동전단위는 1, 5, 10, 50, 100 등으로 구성된 경우가 많다.

하지만 농부 존의 젖소들은 이러한 식상한 동전 단위에 흥미를 느끼지 못하고, 자신들 만의 독특한 동전 단위를 구성하여 사용한다.

농부 존의 젖소들이 사용하는 동전 단위와 지불해야 할 금액이 주어질 때, 그 금액을 단위 동전들로 지불하는 경우의 수를 구하는 프로그램을 작성하시오.

(단, 각 동전의 수는 무한하다.)

Input

첫 번째 줄에 동전의 가지 수와 지불해야할 동전의 액수가 공백으로 구분되어 입력된다.
두 번째 줄에 각 단위 동전이 공백으로 구분되어 입력된다.
(단, 동전의 수는 25이하의 자연수, 지불해야할 금액은 10,000원 이하의 자연수이다. 주어진 모든 금액은 주어진 동전으로 지불가능하다.)

Output

주어진 액수를 지불하는 경우의 수를 한 줄로 출력한다. 출력되는 값은 2^63 - 1을 초과하지 않는다.

IO Example

입력
3 10
1 2 5

출력
10

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]