Description

According to Malcolm’s observations, there are $n$ students in the class. If the ranks of two students differ by at most $k$, then they are friends. If two students are friends and their name lengths are the same, then they are good friends.

Now you are given the names and ranks of these $n$ students. Find how many pairs of good friends there are in the class.

Input Format

The input has $n+1$ lines.

The first line contains two integers $n,k$, representing the number of students in the class and the maximum rank difference allowed for being friends.
The next $n$ lines follow: the $(i+1)$-th line contains a string, the name of the student ranked $i$-th in the class.

Output Format

Output a single line with one integer, the number of pairs of good friends in the class.

4 2
IVA
IVO
ANA
TOM

5

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

2

Hint

Constraints

For all testdata, $3\leqslant n\leqslant 3\times 10^5$, $1\leqslant k\leqslant n$. Each string has length in $[2,20]$ and contains only uppercase English letters.

Source

This problem is from COCI 2012-2013 CONTEST 3 T3 MALCOLM. Using the original testdata settings, the full score is $100$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5