Dollar Dayz

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ways to spend exactly N dollars on unlimited tools priced $1 to $K, where the order of purchases does not matter.

Level: Medium4 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Farmer John goes to Dollar Days at The Cow Store and finds an unlimited number of tools on sale. On his first visit, the tools sell for $1, $2, and $3 each. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each, or 1 tool at $3 and 1 tool at $2. Other combinations exist too, for a total of 5 different ways FJ can spend all his money on tools. They are:

        1 @ US$3 + 1 @ US$2
        1 @ US$3 + 2 @ US$1
        1 @ US$2 + 3 @ US$1
        2 @ US$2 + 1 @ US$1
        5 @ US$1

Write a program that computes the number of ways FJ can spend N dollars at The Cow Store on tools priced $1 to $K (1 ≤ N ≤ 1000, 1 ≤ K ≤ 100).

Input

A single line with two space-separated integers, N and K.

Output

A single line with one integer, the number of different ways FJ can spend his money.

Examples1

Example 1
Input
```
5 3
```
Expected output
```
5
```