Категория с наибольшей медианой оценок

Мобильное приложение собирает отзывы пользователей. Каждый отзыв содержит категорию обращения и целую оценку от 1 до 5.

Для каждой категории определяются количество отзывов c и медиана оценок m. Медиана находится так: все оценки категории сортируются по неубыванию. Если их количество нечётно, медиана равна центральной оценке. Если количество чётно, медиана равна среднему арифметическому двух центральных оценок.

В конце входных данных указан ЗАПРОС — минимальное число отзывов k. Среди категорий, для которых c >= k, требуется вывести название категории с наибольшей медианой оценок.

Если наибольшая медиана достигается у нескольких категорий, выводится лексикографически меньшее название категории. Округление не применяется, так как в ответе выводится название категории. Пустых категорий во входных данных нет, и гарантируется, что хотя бы одна категория содержит не менее k отзывов.

Формат ввода

В первой строке дано целое число n — количество отзывов.

В следующих n строках даны название категории category и оценка rating, разделённые пробелом.

В последней строке дано целое число k — параметр ЗАПРОСА, минимальное количество отзывов в категории.

Формат вывода

Выведите одно название категории, удовлетворяющей запросу и имеющей наибольшую медиану оценок.

Ограничения

1 <= n <= 2000.

1 <= k <= n.

1 <= rating <= 5.

Название категории состоит из строчных латинских букв, его длина от 1 до 20 символов.

Гарантируется, что существует хотя бы одна категория, встречающаяся во входных данных не менее k раз.