멀티버스 Ⅱ

시간 제한2초메모리 제한512 MB

요약

두 우주는 행성 크기의 대소 관계와 동일한 값의 묶음이 같을 때 같다고 하며, M개 우주 중 같은 쌍의 개수를 센다.

난이도: 보통10점 중 4점
유형: 정렬, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

$M$ 개의 우주가 있고, 각 우주에는 1부터 $N$ 까지 번호가 매겨진 행성이 $N$ 개 있다. 행성의 크기를 알고 있을 때, 균등한 우주의 쌍이 몇 개인지 구하려고 한다. 구성이 같고 순서만 다른 우주의 쌍은 한 번만 센다.

두 우주 $A$ 와 $B$ 가 있고, 우주 $A$ 에 있는 행성의 크기는 $A_1, A_2, \dots, A_N$ , 우주 $B$ 에 있는 행성의 크기는 $B_1, B_2, \dots, B_N$ 이라고 하자. 모든 $1 \le i, j \le N$ 에 대해서 두 우주의 행성 크기가 아래 조건을 만족하면, 두 우주를 균등하다고 한다.

$A_i < A_j \rightarrow B_i < B_j$
$A_i = A_j \rightarrow B_i = B_j$
$A_i > A_j \rightarrow B_i > B_j$

입력

첫째 줄에 우주의 개수 $M$ 과 각 우주에 있는 행성의 개수 $N$ 이 주어진다. 둘째 줄부터 $M$ 개의 줄에 공백으로 구분된 행성의 크기가 한 줄에 하나씩 1번 우주부터 차례대로 주어진다.

출력

첫째 줄에 균등한 우주의 쌍의 개수를 출력한다.

제한

$2 \le M \le 100$
$3 \le N \le 10{,}000$
$1 \le$ 행성의 크기 $\le 1{,}000{,}000$

예제3

예제 1
입력
```
2 3
1 3 2
12 50 31
```
예상 출력
```
1
```
예제 2
입력
```
2 3
1 3 2
12 50 10
```
예상 출력
```
0
```

예제 3

입력

예상 출력