문제
훌륭한 자연경관을 가지고 있어서 관광객이 많이 오는 A산에 강이 흐르는데, 강줄기를 따라 직선으로 N개의 시설이 있다.
각각의 시설들은 각자 이름이 하나씩 있다.
A산에 여행하러 온 지헌이는 강줄기를 따라 래프팅을 할 것이다.
지헌이는 래프팅 코스를 정해야 하는데, 래프팅 코스의 길이는 R 이하여야 하고 래프팅 코스의 시작점과 끝점에 있는 두 시설의 이름의 길이가 같아야 한다.
당연히 래프팅 코스는 상류에서 하류 쪽으로 가야 한다.
지헌이는 자신의 조건을 만족시키는 래프팅 코스가 얼마나 많은지 알아보려고 한다. 지헌이를 만족시키는 래프팅 코스의 수를 구해보자.
입력
첫 번째 줄에는 N (3 ≤ N ≤ 300,000)과 R (1 ≤ R ≤ N) 이 주어진다. 두 번째 줄부터 N개의 줄에는 상류에서 하류까지 가면서 나오는 시설들의 이름이 주어진다. 시설의 이름은 2~20개의 알파벳 대문자로 이루어져 있다.
출력
지헌이를 만족시키는 래프팅 코스의 수를 출력한다.
예제1
입력
52
PIZZA
CUTLET
PASTA
BREAD
CHICKEN
출력
2
예제2
입력
63
PENSION
CAFE
HOTEL
JAZZ
MUSICAL
PASTA
출력
2
출처
COCI 2012/2013 contest 3 task 3 Malcolm