Серия превышений заявок

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

Во второй таблице для каждой линии указан её допустимый порог заявок. Строки первой таблицы необходимо сопоставить со строками второй таблицы по коду линии связи.

Для наблюдения с номером i обозначим число заявок через c_i, а порог соответствующей линии через p_i. Определим x_i = 1, если число заявок указано и c_i >= p_i, иначе x_i = 0. Требуется найти наименьший номер t, для которого x_{t-m+1} = x_{t-m+2} = ... = x_t = 1. Это первый момент, когда порог достигнут или превышен m раз подряд. Если такого момента нет, требуется вывести -1.

При равенстве числа заявок и порога наблюдение считается превышающим порог. Пропуск числа заявок обозначается символом -, считается значением x_i = 0 и прерывает серию.

Формат ввода

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

В следующих n строках записаны наблюдения первой таблицы: код линии связи service_id и число заявок request_count. Вместо числа заявок может быть записан символ -.

В следующих k строках записана таблица порогов: код линии связи service_id и целое число threshold.

Каждый код линии из первой таблицы встречается во второй таблице ровно один раз. Порядок строк таблицы порогов не связан с хронологическим порядком наблюдений.

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

Выведите одно целое число t — номер наблюдения, на котором впервые заканчивается серия из m подряд идущих превышений. Нумерация наблюдений начинается с 1.

Если серии длины m нет, выведите -1.

Ограничения

1 <= n <= 2000.

1 <= k <= 2000.

1 <= m <= n.

Код линии связи состоит из строчных латинских букв и цифр, его длина от 2 до 12 символов.

0 <= request_count <= 1000000, если вместо значения не записан символ -.

0 <= threshold <= 1000000.

Коды линий во второй таблице не повторяются.