Порог загрузки для дерева решений

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

Запись с временем загрузки -1 означает пропуск измерения. Такие записи полностью исключаются из построения дерева. Остальные записи могут иметь одинаковое время загрузки.

Для каждого значения параметра min_leaf из запроса требуется найти целочисленный порог t, при котором оба листа содержат не менее min_leaf использованных записей, а взвешенная нечистота Джини минимальна. Левая группа состоит из записей с load_ms <= t, правая — из записей с load_ms > t.

Для группы из k записей, среди которых c0 записей с меткой 0 и c1 записей с меткой 1, нечистота Джини равна G = 1 - (c0 / k)^2 - (c1 / k)^2. Если размеры левой и правой групп равны L и R, а число использованных записей равно N, взвешенная нечистота равна (L / N) * G_left + (R / N) * G_right.

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

Формат ввода

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

В следующих n строках записаны два целых числа load_ms и bounce. Значение bounce равно 0, если посетитель продолжил просмотр, и 1, если посетитель завершил просмотр сразу.

В последней строке записаны m целых чисел min_leaf — значения параметра запроса.

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

Выведите m целых чисел, по одному в строке. Для каждого значения min_leaf выведите найденный порог или -1.

Выводится целое число, округление не применяется.

Ограничения

1 <= n <= 4000.

1 <= m <= 100.

load_ms = -1 или 0 <= load_ms <= 30000.

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

1 <= min_leaf <= n.

Хотя бы одна строка журнала имеет значение load_ms, отличное от -1.