Good Friends

Time limit1sMemory limit128 MB

Summary
Count pairs of students within rank distance K whose names have equal length, given names in rank order.
Level

Medium4 of 10

Topics
Sliding window, Array, Implementation
Solved
No attempts yet

Problem

N students' names are given in rank order. Two students are good friends if the difference between their ranks is at most K and their names have the same length.

Write a program that counts the number of pairs of students who are good friends.

Input

The first line contains N and K. (3 <= N <= 300,000, 1 <= K <= N)

Each of the next N lines contains one student's name in rank order. Every name consists only of uppercase English letters and has length between 2 and 20, inclusive.

Output

Print the number of pairs of students who are good friends.

Examples2

  1. Example 1

    Input
    4 2
IVA
IVO
ANA
TOM
    Expected output
    5

  2. Example 2

    Input
    6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY
    Expected output
    2