Time Limit: 1s
Memory Limit: 128MB
수 천개의 계단을 오르다가 결국 지쳐버린 웰시씨는 고무고무 열매를 먹고 한 번에 최대 m개의 계단을 오를 수 있게 되었다. 웰시씨가 n개의 계단을 오르는 방법은 총 몇 가지인지 계산해보자.
Line 1: 입력의 갯수 N (1≤N≤10000)
Line 2~N: 총 계단 수 n과 한번에 오를 수 있는 최대 계단 수 m (1 ≤ n, m ≤ 20)
Line 1~N: n개의 계단을 최대 m칸까지 오를 수 있을 때 오르는 방법의 수
3 5 2 5 3 5 4
8 13 15
최대 3칸까지 오를 수 있을 때 계단을 오르는 방법의 수 = 맨 마지막에 한 칸 올라가는 방법의 수 + 맨 마지막에 두 칸 올라가는 방법의 수 + 맨 마지막에 세 칸 올라가는 방법의 수