Problem Description

To improve their health, the cows have started doing gymnastics training. Farmer John chose his favorite cow, Bessie, to coach the other $N$ cows, while also evaluating their progress in learning different gymnastics skills.

In each of the $K$ training sessions, Bessie ranks the $N$ cows based on their performance. Later, she became curious about how consistent these rankings are. A pair of different cows is called consistent if one cow performs better than the other in every training session.

Please help Bessie count the number of consistent cow pairs.

Input Format

The first line contains two positive integers $K$ and $N$. The next $K$ lines each contain a permutation of the integers $1 \ldots N$, representing the rankings of the cows (the cows are identified by numbers $1 \ldots N$). If in a line $A$ appears before $B$, it means cow $A$ performed better than cow $B$.

Output Format

Output one line containing the number of consistent cow pairs.

3 4
4 1 2 3
4 1 3 2
4 2 1 3

4

Hint

The consistent cow pairs are $(1,4)$, $(2,4)$, $(3,4)$, and $(1,3)$.

$1 \leq K \leq 10$, $1 \leq N \leq 20$.

Problem by: Nick Wu.

Translated by ChatGPT 5