Edamame Energy Engineering

The biotech startup ICPC (International Cucumber Planting Company) is working on cultivating edamame for fuel. According to the business plan they submitted to venture capitalists, chemically treating edamame that has been specially bred with ICPC's technology using a particular chemical yields fuel ethanol (they originally worked on improving cucumbers, but that did not go well).

The edamame is about to reach harvest season. The pod of this edamame holds M beans in a row, and each bean has different properties, so originally each would need a different chemical treatment.

There are N kinds of chemicals used for chemical treatment. Each bean has 2 properties, and if either one of them is satisfied, it can be turned into fuel. Properties come in two types: "uses a certain chemical" and "does not use a certain chemical".

• Property P(x): chemical of kind x is effective (treatable by using chemical of kind x)
• Property Q(x): inhibited by chemical of kind x, it has a self-degrading enzyme effective on that bean (treatable if chemical of kind x is not used)

For example, if a bean has properties P(x) and Q(y), then this bean can be treated by using chemical of kind x, and even if chemical of kind x is not used, it can be treated as long as chemical of kind y is not used. Also, the 2 properties a bean has may be of the same type; for example, if it has properties P(x) and P(y), then this bean can be treated by using chemical of kind x or y.

After long research and development, ICPC's funds are running out, so they had no resources left to invest in equipment that takes out edamame one bean at a time and performs appropriate treatment on each. As an alternative, they decided to adopt a process that uses a treatment liquid made by mixing 0 or more kinds of chemicals, discards 0 or more consecutive beans from both ends of the edamame, and treats all the remaining beans in the middle together. At this time, it is known that the chemicals and edamame cause no interactions other than those expressed by the properties. However, if any untreated beans remain, it interferes with later processes, so this is not allowed.

Of course, to raise the equipment's yield, it is better to discard as few beans as possible. Your job as ICPC's software engineer is to write a program that plans so that as many beans as possible can be used by appropriately choosing the kinds of chemicals used in the treatment liquid.

For example, in the first dataset of the sample input, using a treatment liquid that mixes chemicals of kinds 1 and 2 allows treating the 1st through 3rd beans. However, with any of the 4 total treatment liquids that use or do not use chemicals of kinds 1 and 2 respectively, one bean cannot be treated. Therefore the answer for this dataset is 3. As in the second dataset, note that one bean may have the same property duplicated. In this case too, it can be treated if either of the two conditions is satisfied. In the third dataset, using a treatment liquid that uses no chemical allows treating all beans.

The input consists of at most 50 datasets. Each dataset is given in the following format.

N M
a1 b1
...
aM bM

The first line gives the number of chemical kinds N (1 ≤ N ≤ 2000) and the number of beans in the edamame M (1 ≤ M ≤ 2000) in this order. The following M lines give information about the beans, one line each. The (1 + i)-th line gives two integers ai and bi representing the properties of the i-th bean counting from the end. If this integer is x, it satisfies -N ≤ x ≤ N, x ≠ 0; when x is positive it means the i-th bean can be treated with chemical of kind x, that is, it has property P(x), and when x is negative it means the i-th bean can be treated if chemical of kind |x| is not used, that is, it has property Q(|x|).

The end of input is represented by a line consisting of two 0s.

For each dataset, output the maximum number of beans that can be used for treatment on one line.