시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 462 103 84 30.216%

문제

상근이는 환갑을 바라보던 나이에 수능 시험을 다시보고 교대에 입학했고, 초등학교 선생님으로 취직했다.

상근: 요즘 애들은 친구를 사귀지 않나봐. 내가 앞에서 보고 있으면, 친구가 있는 학생이 별로 없는 것 같아.

??: 오빠! 오빠는 말콤의 친구와 성적이라는 책 안 읽어 봤어? 이 책에는 성적과 친구가 무슨 관계가 있는지 나와. 요즘 애들은 친구를 사귀기 전에 먼저 그 친구의 반 등수를 살펴봐. 말콤은 이 연구를 하기 위해서 6년동안 초등학교에서 선생님으로 위장 했었지. 하지만, 6년이라는 시간을 초등학교에서 보냈지만, 그 사람은 결국 결론을 얻지 못했어.

상근: 근데?

??: 내 말 아직 안끝났어. 말콤이 어느날 자신이 초등학생이 되어 학교를 활보하는 꿈을 꾸었어. 근데 잠을 깨고 나니 내가 꿈을 꾸고 초등학생이 된건지, 아니면 초등학생이 꿈을 꾸고 지금의 내가 되어있는지를 모르겠는거야. 그래서 말콤은 상식적인 사고 방식에 큰 의문을 가졌지. 그 때 말콤은 깨달았던거야. 초등학교 친구는 부질없구나. 그제서야 알게된거야. 모든 학생은 자신과 반 등수의 차이가 K를 넘으면 친구가 아니라는거.

상근: 아? 근데 K는 어떻게 구해?

??: K는 문제에서 주어지지. 근데, 더 중요한 사실이 있어. 친구와 좋은 친구의 차이야. 말콤이 친구와 성적을 쓰고 2년 뒤에 낸 책인 좋은 친구라는 책에는 좋은 친구는 이름의 길이가 같아야 된다는 말이 나와.

상근: 아! 그럼 난 오늘 집에 가서 우리 반에 좋은 친구가 몇 쌍이나 있는지 구해봐야 겠어!

상근이네 반의 N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 프로그램을 작성하시오. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구이다.

입력

첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다.

출력

첫째 줄에 좋은 친구의 수를 출력한다.

예제 입력 1

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

예제 출력 1

2

힌트

W3sicHJvYmxlbV9pZCI6IjMwNzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4OGJcdWM3NDAgXHVjZTVjXHVhZDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNjU4XHVhYzExXHVjNzQ0IFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YjM1OCBcdWIwOThcdWM3NzRcdWM1ZDAgXHVjMjE4XHViMmE1IFx1YzJkY1x1ZDVkOFx1Yzc0NCBcdWIyZTRcdWMyZGNcdWJjZjRcdWFjZTAgXHVhZDUwXHViMzAwXHVjNWQwIFx1Yzc4NVx1ZDU1OVx1ZDU4OFx1YWNlMCwgXHVjZDA4XHViNGYxXHVkNTU5XHVhZDUwIFx1YzEyMFx1YzBkZFx1YjJkOFx1YzczY1x1Yjg1YyBcdWNkZThcdWM5YzFcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmYzogXHVjNjk0XHVjOTk4IFx1YzU2MFx1YjRlNFx1Yzc0MCBcdWNlNWNcdWFkNmNcdWI5N2MgXHVjMGFjXHVhZGMwXHVjOWMwIFx1YzU0YVx1YjA5OFx1YmQxMC4gXHViMGI0XHVhYzAwIFx1YzU1ZVx1YzVkMFx1YzExYyBcdWJjZjRcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTc0LCBcdWNlNWNcdWFkNmNcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWJjYzRcdWI4NWMgXHVjNWM2XHViMjk0IFx1YWM4MyBcdWFjMTlcdWM1NDQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdD8/OiBcdWM2MjRcdWJlNjAhIFx1YzYyNFx1YmU2MFx1YjI5NCBcdWI5ZDBcdWNmNjRcdWM3NTggXHVjZTVjXHVhZDZjXHVjNjQwIFx1YzEzMVx1YzgwMVx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWNjNDUgXHVjNTQ4IFx1Yzc3ZFx1YzViNCBcdWJkMjRcdWM1YjQ/IFx1Yzc3NCBcdWNjNDVcdWM1ZDBcdWIyOTQgXHVjMTMxXHVjODAxXHVhY2ZjIFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWJiMzRcdWMyYTggXHVhZDAwXHVhY2M0XHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWIwOThcdWM2NDAuIFx1YzY5NFx1Yzk5OCBcdWM1NjBcdWI0ZTRcdWM3NDAgXHVjZTVjXHVhZDZjXHViOTdjIFx1YzBhY1x1YWRjMFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHViYTNjXHVjODAwIFx1YWRmOCBcdWNlNWNcdWFkNmNcdWM3NTggXHViYzE4IFx1YjRmMVx1YzIxOFx1Yjk3YyBcdWMwYjRcdWQzYjRcdWJkMTAuIFx1YjlkMFx1Y2Y2NFx1Yzc0MCBcdWM3NzQgXHVjNWYwXHVhZDZjXHViOTdjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgNlx1YjE0NFx1YjNkOVx1YzU0OCBcdWNkMDhcdWI0ZjFcdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgXHVjMTIwXHVjMGRkXHViMmQ4XHVjNzNjXHViODVjIFx1YzcwNFx1YzdhNSBcdWQ1ODhcdWM1YzhcdWM5YzAuIFx1ZDU1OFx1YzljMFx1YjljYywgNlx1YjE0NFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDA4XHViNGYxXHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjIFx1YmNmNFx1YjBjOFx1YzljMFx1YjljYywgXHVhZGY4IFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWFjYjBcdWFkNmQgXHVhY2IwXHViODYwXHVjNzQ0IFx1YzViYlx1YzljMCBcdWJhYmJcdWQ1ODhcdWM1YjQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmYzogXHVhZGZjXHViMzcwPzxcL3A+XHJcblxyXG48cD5cclxuXHQ/PzogXHViMGI0IFx1YjlkMCBcdWM1NDRcdWM5YzEgXHVjNTQ4XHViMDVkXHViMGFjXHVjNWI0LiBcdWI5ZDBcdWNmNjRcdWM3NzQgXHVjNWI0XHViMjkwXHViMGEwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWNkMDhcdWI0ZjFcdWQ1NTlcdWMwZGRcdWM3NzQgXHViNDE4XHVjNWI0IFx1ZDU1OVx1YWQ1MFx1Yjk3YyBcdWQ2NWNcdWJjZjRcdWQ1NThcdWIyOTQgXHVhZmM4XHVjNzQ0IFx1YWZiOFx1YzVjOFx1YzViNC4gXHVhZGZjXHViMzcwIFx1YzdhMFx1Yzc0NCBcdWFlNjhcdWFjZTAgXHViMDk4XHViMmM4IFx1YjBiNFx1YWMwMCBcdWFmYzhcdWM3NDQgXHVhZmI4XHVhY2UwIFx1Y2QwOFx1YjRmMVx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWI0MWNcdWFjNzRcdWM5YzAsIFx1YzU0NFx1YjJjOFx1YmE3NCBcdWNkMDhcdWI0ZjFcdWQ1NTlcdWMwZGRcdWM3NzQgXHVhZmM4XHVjNzQ0IFx1YWZiOFx1YWNlMCBcdWM5YzBcdWFlMDhcdWM3NTggXHViMGI0XHVhYzAwIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWJhYThcdWI5NzRcdWFjYTBcdWIyOTRcdWFjNzBcdWM1N2MuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWI5ZDBcdWNmNjRcdWM3NDAgXHVjMGMxXHVjMmRkXHVjODAxXHVjNzc4IFx1YzBhY1x1YWNlMCBcdWJjMjlcdWMyZGRcdWM1ZDAgXHVkMDcwIFx1Yzc1OFx1YmIzOFx1Yzc0NCBcdWFjMDBcdWM4NGNcdWM5YzAuIFx1YWRmOCBcdWI1NGMgXHViOWQwXHVjZjY0XHVjNzQwIFx1YWU2OFx1YjJlY1x1YzU1OFx1YjM1OFx1YWM3MFx1YzU3Yy4gXHVjZDA4XHViNGYxXHVkNTU5XHVhZDUwIFx1Y2U1Y1x1YWQ2Y1x1YjI5NCBcdWJkODBcdWM5YzhcdWM1YzZcdWFkNmNcdWIwOTguIFx1YWRmOFx1YzgxY1x1YzExY1x1YzU3YyBcdWM1NGNcdWFjOGNcdWI0MWNcdWFjNzBcdWM1N2MuIFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHVjNzkwXHVjMmUwXHVhY2ZjIFx1YmMxOCBcdWI0ZjFcdWMyMThcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIEtcdWI5N2MgXHViMTE4XHVjNzNjXHViYTc0IFx1Y2U1Y1x1YWQ2Y1x1YWMwMCBcdWM1NDRcdWIyYzhcdWI3N2NcdWIyOTRcdWFjNzAuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmYzogXHVjNTQ0PyBcdWFkZmNcdWIzNzAgS1x1YjI5NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVhZDZjXHVkNTc0PzxcL3A+XHJcblxyXG48cD5cclxuXHQ/PzogS1x1YjI5NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwLiBcdWFkZmNcdWIzNzAsIFx1YjM1NCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHVjMGFjXHVjMmU0XHVjNzc0IFx1Yzc4OFx1YzViNC4gXHVjZTVjXHVhZDZjXHVjNjQwIFx1Yzg4Ylx1Yzc0MCBcdWNlNWNcdWFkNmNcdWM3NTggXHVjYzI4XHVjNzc0XHVjNTdjLiBcdWI5ZDBcdWNmNjRcdWM3NzQgXHVjZTVjXHVhZDZjXHVjNjQwIFx1YzEzMVx1YzgwMVx1Yzc0NCBcdWM0ZjBcdWFjZTAgMlx1YjE0NCBcdWI0YTRcdWM1ZDAgXHViMGI4IFx1Y2M0NVx1Yzc3OCBcdWM4OGJcdWM3NDAgXHVjZTVjXHVhZDZjXHViNzdjXHViMjk0IFx1Y2M0NVx1YzVkMFx1YjI5NCBcdWM4OGJcdWM3NDAgXHVjZTVjXHVhZDZjXHViMjk0IFx1Yzc3NFx1Yjk4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVhYzE5XHVjNTQ0XHVjNTdjIFx1YjQxY1x1YjJlNFx1YjI5NCBcdWI5ZDBcdWM3NzQgXHViMDk4XHVjNjQwLjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmM6IFx1YzU0NCEgXHVhZGY4XHViN2ZjIFx1YjA5YyBcdWM2MjRcdWIyOTggXHVjOWQxXHVjNWQwIFx1YWMwMFx1YzExYyBcdWM2YjBcdWI5YWMgXHViYzE4XHVjNWQwIFx1Yzg4Ylx1Yzc0MCBcdWNlNWNcdWFkNmNcdWFjMDAgXHViYTg3IFx1YzMwZFx1Yzc3NFx1YjA5OCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTc0XHViZDEwXHVjNTdjIFx1YWNhMFx1YzViNCE8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMTI0IFx1YmMxOFx1Yzc1OCBOXHViYTg1IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjMTMxXHVjODAxXHVjMjFjXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzg4Ylx1Yzc0MCBcdWNlNWNcdWFkNmNcdWFjMDAgXHViYTg3IFx1YzMwZFx1Yzc3NFx1YjA5OCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Yzg4Ylx1Yzc0MCBcdWNlNWNcdWFkNmNcdWIyOTQgXHViNGYxXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCBLXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3M2NcdWJhNzRcdWMxMWMgXHVjNzc0XHViOTg0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVjZTVjXHVhZDZjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IE4gJmxlOyAzMDAsMDAwLCAxICZsZTsgSyAmbGU7IE4pIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIxMjQgXHViYzE4IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjMTMxXHVjODAxXHVjMjFjXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViOTg0XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgMlx1YWUwMFx1Yzc5MCB+IDIwXHVhZTAwXHVjNzkwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODhiXHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwNzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNQUxDT0xNIiwiZGVzY3JpcHRpb24iOiI8cD5TaW5jZSB0ZWFjaGVyIEhlcmthYmUgaGFzIHN0YXJ0ZWQgcmFua2luZyBoaXMgTiBzdHVkZW50cywgdGhlIG51bWJlciBvZiBmcmllbmRzaGlwcyBpbiBoaXMgY2xhc3MgaGFzIHNoYXJwbHkgZmFsbGVuLiBUaGUgc3R1ZGVudHMgbmVhciB0aGUgYm90dG9tIG9mIHRoZSByYW5raW5ncyBsaXN0IGhhdmUgYmVjb21lIGplYWxvdXMgb2YgdGhlIHRvcCBzdHVkZW50cywgd2hpbGUgdGhlIHRvcCBzdHVkZW50cyBzdGFydGVkIGxvb2tpbmcgZG93biBvbiB0aGVpciBsZXNzIHN1Y2Nlc3NmdWwgY29sbGVhZ3Vlcy48XC9wPlxyXG5cclxuPHA+QWNjb3JkaW5nIHRvIE1hbGNvbG0mIzM5O3Mgb2JzZXJ2YXRpb25zLCB0aGUgZm9sbG93aW5nIHJ1bGUgaG9sZHM6IHR3byBzdHVkZW50cyBhcmUgZnJpZW5kcyBpZiB0aGVpciByYW5rcyBhcmUgY2xvc2UgZW5vdWdoLCBtb3JlIHByZWNpc2VseSwgaWYgdGhleSBkaWZmZXIgYnkgYXQgbW9zdCBLLiBGb3IgZXhhbXBsZSwgaWYgSyA9IDEsIHRoZW4gb25seSBuZWlnaGJvdXJpbmcgc3R1ZGVudHMgb24gdGhlIHJhbmtpbmdzIGxpc3QgYXJlIGZyaWVuZHMuIEZ1cnRoZXJtb3JlLCB0d28gc3R1ZGVudHMgYXJlIGdvb2QgZnJpZW5kcyBpZiB0aGV5IGFyZSBmcmllbmRzIGFuZCB0aGVpciBuYW1lcyBoYXZlIHRoZSBzYW1lIGxlbmd0aC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGNhbGN1bGF0ZSB0aGUgbnVtYmVyIG9mIHBhaXJzIG9mIGdvb2QgZnJpZW5kcyBpbiB0aGlzIGdpZnRlZCBjbGFzcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgTiAoMyAmbGU7IE4gJmxlOyAzMDAgMDAwKSBhbmQgSyAoMSAmbGU7IEsgJmxlOyBOKSwgZnJvbSB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGEgc2luZ2xlIHN0dWRlbnQmIzM5O3MgbmFtZS4gVGhlIG5hbWVzIGFyZSBnaXZlbiBpbiB0aGUgb3JkZXIgdGhleSBhcHBlYXIgb24gdGhlIHJhbmtpbmdzIGxpc3QuIFRoZXkgY29uc2lzdCBvZiBiZXR3ZWVuIDIgYW5kIDIwIChpbmNsdXNpdmUpIHVwcGVyY2FzZSBFbmdsaXNoIGxldHRlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHBhaXJzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=