Changing a Bill with Coins

A shop cash register has k kinds of coins. For the i-th coin kind, each coin is worth p_i, and there are n_i coins.

The owner wants to exchange one bill worth T won into these coins. You may use at most the available count of each coin kind. If the number of coins used from each kind is the same, the order of the coins does not create a different way.

Given T, k, and each coin kind's value p_i and count n_i, compute the number of ways to make exactly T won. It is guaranteed that the answer does not exceed 2^31 - 1.

The first line contains the bill amount T, where 0 < T <= 10,000.

The second line contains the number of coin kinds k, where 0 < k <= 100.

Each of the next k lines contains the value p_i and count n_i of one coin kind, separated by one space. 0 < p_i <= T and 0 < n_i <= 1,000.

Print the number of ways to make T won with the coins. If there is no way, print 0.