Порог разбиения по рейтингу шахматистов

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

Строки второй таблицы сопоставляются со строками первой по идентификатору игрока. Если рейтинг игрока равен -1, его рейтинг неизвестен, поэтому все строки с этим игроком не участвуют в выборе разбиения. Повторы идентификаторов во второй таблице означают несколько партий одного игрока и учитываются по отдельности.

Рассматриваются пороги t, равные известным значениям рейтинга. Порог делит все учитываемые строки результатов на левую группу с рейтингом rating <= t и правую группу с рейтингом rating > t. Разбиение разрешено только тогда, когда в каждой группе не менее k строк.

Для группы из s строк, среди которых w побед, используется индекс Джини: G = 1 - (w / s)^2 - ((s - w) / s)^2 = 2w(s-w) / s^2. Для допустимого порога вычисляется взвешенная нечистота Q(t) = s_left * G_left + s_right * G_right. Требуется вывести порог с минимальным значением Q(t). Это равносильно выбору разбиения с наибольшим уменьшением индекса Джини относительно исходной группы.

При равенстве минимальных значений Q(t) выбирается меньший порог. Если допустимого порога нет, выводится -1.

Формат ввода

В первой строке заданы три целых числа n, m и k — число строк в таблице игроков, число строк в таблице результатов и минимальный допустимый размер каждой группы.

В следующих n строках содержатся таблица игроков: идентификатор игрока player_id и его рейтинг rating.

В следующих m строках содержатся таблица результатов: идентификатор игрока player_id и число result. Значение result = 1 означает победу, значение result = 0 означает отсутствие победы.

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

Выведите одно целое число: выбранный порог рейтинга или -1, если допустимого разбиения нет.

Ограничения

1 <= n <= 4000.

1 <= m <= 4000.

1 <= k <= m.

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

Идентификаторы игроков в первой таблице попарно различны.

Каждый идентификатор из второй таблицы присутствует в первой таблице.

rating = -1 или 0 <= rating <= 3000.

result равно 0 или 1.

После исключения строк с неизвестным рейтингом может не остаться ни одной строки. В этом случае допустимого разбиения нет.

Дробная часть нигде не округляется: выводится только целый порог рейтинга или -1.