{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAs a basketball fan, Mike is also fond of collecting basketball player cards. But as a student, he can not always get the money to buy new cards, so sometimes he will exchange with his friends for cards he likes. Of course, different cards have different value, and Mike must use cards he owns to get the new one. For example, to get a card of value 10$, he can use two 5$ cards or three 3$ cards plus one 1$ card, depending on the kinds of cards he have and the number of each kind of card. And Sometimes he will involve unfortunately in a bad condition that he has not got the exact value of the card he is looking for (fans always exchange cards for equivalent value).\u003c/p\u003e\n\n\u003cp\u003eHere comes the problem, given the card value he plans to get and the cards he has, Mike wants to fix how many ways he can get it. So it\u0027s you task to write a program to figure it out.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eThe problem consists of multiple test cases, terminated by \u003cb\u003eEOF\u003c/b\u003e. There\u0027s a blank line between two inputs.\u003c/p\u003e\n\u003cp\u003eThe first line of each test case gives \u003cb\u003en\u003c/b\u003e, the value of the card Mike plans to get and \u003cb\u003em\u003c/b\u003e, the number of different kinds of cards Mike has. \u003cb\u003en\u003c/b\u003e will be an integer number between 1 and 1000. \u003cb\u003em\u003c/b\u003e will be an integer number between 1 and 10.\u003c/p\u003e\n\u003cp\u003eThe next \u003cb\u003em\u003c/b\u003e lines give the information of different kinds of cards Mike have. Each line contains two integers, \u003cb\u003eval\u003c/b\u003e and \u003cb\u003enum\u003c/b\u003e, representing the value of this kind of card, and the number of this kind of card Mike have.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003e\u003ci\u003eNote:\u003c/i\u003e\u003c/b\u003e different kinds of cards will have different value, each \u003cb\u003eval\u003c/b\u003e and \u003cb\u003enum\u003c/b\u003e will be an integer greater than zero.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eFor each test case, output in one line the number of different ways Mike could exchange for the card he wants. You can be sure that the output will fall into an integer value.\u003c/p\u003e\n\u003cp\u003eOutput a blank line between two test cases.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\n\u003cpre\u003e5 2\n2 1\n3 1\n\n10 5\n10 2\n7 2\n5 3\n2 2\n1 5\n\u003c/pre\u003e\n\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\n\u003cpre\u003e1\n\n7\n\u003c/pre\u003e\n\n\u003cbr\u003e\n"}}]}