Student Z finds playing chess very interesting, so he decided to create a game called "Everyday Love Chess". "Everyday Love Chess" is a card game where players need to combine cards from their inventory into a deck to compete against other players.

Each card in this game has two values: attack power and defense value. Card A can defeat card B if and only if the attack power of card A is greater than or equal to the defense value of card B.

A deck in this game consists of exactly three distinct cards, placed in order into three card slots. For the sake of fairness, three cards can form a deck if and only if:

• The card in slot 1 can defeat the card in slot 2.
• The card in slot 2 can defeat the card in slot 3.
• The card in slot 3 can defeat the card in slot 1.

After development, Student Z invited Student H to help test the game and gave him $n$ initial cards.

Now, Student H wants to know how many essentially different decks he can form. Two decks are different if and only if there is at least one card slot that contains a different card.

Input

Read data from standard input.

The first line of input contains two integers $s$ and $n$, representing the subtask number and the number of cards, respectively. For the sample, $s$ indicates that the sample shares the same constraints as test case $s$.

The next $n$ lines each contain two integers $a_i, d_i$, representing the attack power and defense value of the $i$-th card, respectively.

Output

Output to standard output.

Output a single integer representing the total number of essentially different decks Student H can form.

Examples

Input

1 10
7 4
18 18
10 15
12 3
12 15
9 7
10 1
3 19
11 7
8 13

Output

60

Example 2

See ex_2.in and ex_2.ans in the download directory.

This sample satisfies the conditions of subtask 4.

Example 3

See ex_3.in and ex_3.ans in the download directory.

This sample satisfies the conditions of subtask 6.

Subtasks

For all test data, it is guaranteed that $1 \le n \le 2 \times 10^{5}$ and $1 \le a_i, d_i \le 2 \times n$.

Special Property: It is guaranteed that $\forall 1\le i \le n, 1\le a_i, d_i \le 500$.