Little Chris is having a nightmare. Even in dreams all he thinks about is math.

Chris dreams about m binary strings of length n, indexed with numbers from 1 to m. The most horrifying part is that the bits of each string are ordered in either ascending or descending order. For example, Chris could be dreaming about the following 4 strings of length 5:

<image>

The Hamming distance H(a, b) between two strings a and b of length n is the number of positions at which the corresponding symbols are different. 

Сhris thinks that each three strings with different indices constitute a single triple. Chris's delusion is that he will wake up only if he counts the number of such string triples a, b, c that the sum H(a, b) + H(b, c) + H(c, a) is maximal among all the string triples constructed from the dreamed strings.

Help Chris wake up from this nightmare!

Input

The first line of input contains two space-separated integers n and m (1 ≤ n ≤ 109; 3 ≤ m ≤ 105), the length and the number of strings. The next m lines contain the description of the strings. The i-th line contains two space-separated integers si and fi (0 ≤ si ≤ 1; 1 ≤ fi ≤ n), the description of the string with index i; that means that the first fi bits of the i-th string are equal to si, and the remaining n - fi bits are equal to 1 - si. There can be multiple equal strings in Chris's dream.

Output

Output a single integer, the number of such string triples among the given that the sum of the Hamming distances between the strings of the triple is maximal.

Examples

Input

5 4
0 3
0 5
1 4
1 5


Output

3


Input

10 4
1 5
0 5
0 5
1 5


Output

4
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long num[2];
map<int, int> cnt[2];
int best_dist = -1;
long long best_total = 0;
void check_val(int dist, long long total) {
  if (total == 0) return;
  if (dist > best_dist)
    best_dist = dist, best_total = total;
  else if (dist == best_dist)
    best_total += total;
}
void calc_equal(int i) {
  long long k = num[i];
  auto &a = cnt[i];
  if (a.size() == 1) {
    check_val(0, k * (k - 1) * (k - 2) / 6);
    return;
  }
  auto it0 = a.begin();
  auto it1 = --a.end();
  int dist = 2 * (it1->first - it0->first);
  long long c0 = it0->second, c1 = it1->second;
  long long total = c0 * c1 * (k - c0 - c1);
  total += c0 * (c0 - 1) / 2 * c1;
  total += c1 * (c1 - 1) / 2 * c0;
  check_val(dist, total);
}
void calc_unequal(int i, int j) {
  long long ki = num[i], kj = num[j];
  auto &ai = cnt[i], &aj = cnt[j];
  long long prev = 0;
  auto it = ai.begin();
  for (auto &val : aj) {
    while (it != ai.end() && it->first <= val.first) prev += it->second, it++;
    if (it != ai.end()) {
      int dist = 2 * (n - it->first + val.first);
      long long k = it->second;
      long long total = val.second * (k * (k - 1) / 2 + k * (ki - prev - k));
      check_val(dist, total);
    }
  }
  prev = 0;
  it = ai.begin();
  for (auto &val : aj) {
    while (it != ai.end() && it->first < val.first) prev += it->second, it++;
    if (it != ai.begin()) it--, prev -= it->second;
    if (it->first < val.first) {
      int dist = 2 * (n - val.first + it->first);
      long long k = it->second;
      long long total = val.second * (k * (k - 1) / 2 + k * prev);
      check_val(dist, total);
    }
  }
  prev = 0;
  it = ai.begin();
  for (auto &val : aj) {
    while (it != ai.end() && it->first < val.first) prev += it->second, it++;
    if (it != ai.end()) {
      int dist = 2 * n;
      long long k = it->second;
      long long total = prev * (ki - prev);
      if (it->first == val.first)
        total += k * (k - 1) / 2 + k * (ki - prev - k);
      total *= val.second;
      check_val(dist, total);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int s, f;
    scanf("%d%d", &s, &f);
    num[s]++;
    cnt[s][f]++;
  }
  for (int i = 0; i < 2; i++)
    if (num[i] > 2) calc_equal(i);
  for (int i = 0; i < 2; i++)
    if (num[i] > 1 && num[1 - i] > 0) calc_unequal(i, 1 - i);
  printf("%lld\n", best_total);
}
