SPOJ Brasil

A OBI (Organização Brasileira dos Índios) promoverá um festival indígena, onde várias tribos irão se reunir e fazer demonstrações de cultura, como artesanato, danças, pinturas, comidas e etc.

Uma das tribos é a dos Tunak Tunak, que possuem uma apresentação de dança muito peculiar. Nessa dança, existem N toras de madeira encrustadas no chão, dispostas de maneira circ;ular e igualmente espaçadas. Em algumas dessas toras fica um índio, olhando em sentido horário ou anti-horário.

A cada batida do tambor, os índios pulam para a próxima tora (que depende da direção para onde ele está olhando no momento). Durante a dança, porém, algumas coisas podem acontecer:

• Dois índios que pulam em sentidos opostos caem na mesma tora ao mesmo tempo. Nesse caso, ambos permanecem nas toras, mas passam a pular na direção contrária a partir da próxima batida de tambor (isso é, quem estava pulando em sentido horário passa a pular em sentido anti-horário, e vice-versa)
• Dois índios em toras consecutivas vão pular um em direção ao outro. Nesse caso, os índios simplesmente não pulam (para não causar nenhum acidente), e, assim como no caso anterior, passam a pular no sentido contrário a partir da próxima batida de tambor.

Note que se o índio não pula e inverte seu sentido, mas ao mesmo tempo um outro índio cair na mesma tora no sentido contrário, caimos no primeiro caso, e ambos os índios na tora invertem seus sentidos (assim, o índio que estava na tora anteriormente inverte seu sentido novamente).

A dança termina quando as toras ocupadas por um índio são exatamente as mesmas toras ocupadas no início da dança, não importando qual índio está em cada tora e nem os sentidos para onde eles estão pulando.

A figura abaixo ilustra (a) uma configuração inicial com oito toras e seis índios; (b) a posição dos índios após uma batida de tambor; e (c) a posição dos índios após duas batidas de tambor.

Tarefa

Os índios querem se preparar para a dança e precisam saber quanto tempo ela vai durar.

Para isso, você deverá escrever um programa que, dados a quantidade de toras que serão utilizadas, a quantidade de índios e a posição inicial de cada um, calcule quantas batidas de tambor levará para que a dança termine.

Entrada

A primeira linha da entrada possui 2 inteiros: N (3 ≤ N ≤ 1.000.000) e E (1 ≤ E ≤ 1000), que são, respectivamente, a quantidade de toras e a quantidade de índios que irão dançar (E ≤ N). As próximas E linhas contém, cada uma, a descrição da posição inicial de cada índio. Cada linha possui dois inteiros: V (1 ≤ V ≤ N) e D (D = 1 ou D = -1) que representam, respectivamente, o número da tora onde o índio inicia e seu sentido inicial (1 se horário, -1 se anti-horário). A numeração das toras obedece o sentido horário. No início da dança uma tora terá, no máximo, um índio.

Saída

Seu programa deverá exibir um número inteiro representando a quantidade de batidas de tambor necessárias para que a dança acabe.

Exemplo

Entrada
6 4
2 1
3 1
5 1
6 1


Saída
3

Entrada
3 1
2 -1

Saída
3

Entrada

8 6
2 -1
3 1
4 -1
6 1
7 -1
8 1

Saída
4