| Codeforces Round 238 (Div. 1) |
|---|
| Закончено |
Маленькому Крису снится кошмар. Даже во снах все его мысли — только о математике.
Крису снятся 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
