Топ-k самых частых тегов

Дан список из n тегов вакансий. Выведите k самых частых тегов. Если у тегов одинаковая частота, раньше идёт тот, что меньше лексикографически (по кодам символов). Если различных тегов меньше k, выведите все.

Ввод: в первой строке n и k (1 ≤ n ≤ 2500, 1 ≤ k ≤ n), во второй n тегов через пробел. Тег состоит из строчных латинских букв, длина от 1 до 10.

Вывод: до k строк вида тег частота.

Пример 1

Ввод:

8 2
js go py js sql go js py

Вывод:

js 3
go 2

Пример 2

Ввод:

3 5
b a c

Вывод:

a 1
b 1
c 1