E. Тройки Хемминга
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Маленькому Крису снится кошмар. Даже во снах все его мысли — только о математике.

Крису снятся m двоичных строк длины n, пронумерованных от 1 до m. Самое страшное то, что биты каждой из этих строк упорядочены либо по возрастанию, либо по убыванию. Например, Крис может видеть во сне следующие 4 строки длины 5:

Расстояние Хемминга H(a, b) между двумя строками a и b длины n — это количество позиций, на которых соответствующие символы в этих строках отличаются.

Крис считает, что любые три строки с различными номерами образуют тройку. Он убедил себя в том, что проснется, только если посчитает количество таких троек строк a, b, c, что сумма H(a, b) + H(b, c) + H(c, a) максимальна среди всех троек строк из приснившихся ему строк.

Помогите Крису проснуться от кошмара! Посчитайте для него это количество.

Входные данные

В первой строке содержатся два целых числа через пробел, n и m (1 ≤ n ≤ 109; 3 ≤ m ≤ 105), длина каждой двоичной строки и количество строк. В следующих m строках задано описание строк. В i-й строке содержатся два целых числа через пробел, si и fi (0 ≤ si ≤ 1; 1 ≤ fi ≤ n), — описание строки с номером i; пара чисел si, fi означает, что первые fi битов i-й строки равны si, а остальные n - fi битов равны 1 - si. Обратите внимание, что Крис может видеть также и одинаковые строки в своем сне.

Выходные данные

Выведите единственное целое число — количество таких троек строк среди данных, что сумма расстояний Хемминга между строками тройки максимальна среди всех троек строк из приснившихся ему строк.

Примеры
Входные данные
5 4
0 3
0 5
1 4
1 5
Выходные данные
3
Входные данные
10 4
1 5
0 5
0 5
1 5
Выходные данные
4