## Goal

Given a voucher and a list of products, find the number of combinations of products that match with the exact amount of money available on the voucher.

Rule : product can be picked 0, 1, 2 or 3 times.

Output : print the number of different combinations of products.

Example:

Given the list of products:

- bread 90

- green salad 115

- sugar 750g 95

- rice 500g 299

If I have an amount of 300 cents on my voucher, I can only buy:

1 bread + 1 green salad + 1 bag of sugar => 90 + 115 + 95 = 300 cents

So the answer is 1 combination of products.

All prices are in cents .
Input

**Line 1:** An integer `v` for the voucher value in cents

**Line 2:** An integer `n` for the number of products

**Next **`n` lines: string `l` and `p` for the label and price of each product in cents

Output

`c` Number of different combinations of products that you can buy.

Example

Input

300
4
bread 90
green salad 115
sugar 750g 95
rice 500g 299