명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n_1, n_2, … , n_k개 씩 들어있다.

가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다.

이때, 동전 교환 방법은 여러 가지가 있을 수 있다.

예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때,

20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.

20 = 10×2

20 = 10×1 + 5×2

20 = 10×1 + 5×1 + 1×5

20 = 5×3 + 1×5

입력으로 지폐의 금액 T, 동전의 가지 수 k, 각 동전 하나의 금액 p_i와 개수 n_i가 주어질 때 (i=1, 2,…, k)

지폐를 동전으로 교환하는 방법의 가지 수를 계산하는 프로그램을 작성하시오.

방법의 수는 2^{31} 미만으로 가정한다.

동전 바꿔주기 timer 1s memory 128MB

동전 바꿔주기 1s 128MB