ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2010

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

K. Мужья в магазине

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Марк вернулся домой после тяжёлого рабочего дня. Жена вместо того, чтобы накормить ужином, отправила его за хлебом. Когда Марк зашёл в ближайший магазин, он увидел длинную очередь из таких же несчастных мужей, как и он. Марк встал в конец очереди. К счастью, очередь двигалась достаточно быстро  — каждому из этих мужей дома заказали только один вид товара.
Когда очередной муж подходит к прилавку и узнаёт у продавщицы, что в наличии есть нужное ему количество товара, он покупает его и уходит. Если продавщица отвечает ему, что такого товара совсем не осталось, то он сильно расстраивается и уходит домой с пустыми руками. Если же такого товара осталось меньше, чем нужно… Тут не обойтись без консультации жены. Чтобы не задерживать очередь, покупатель пропускает вперёд одного человека, вставая непосредственно за ним, и звонит жене. Жена всегда советует купить весь остаток товара. После этого он снова подходит к прилавку и, если количество товара, имеющееся в наличии, не изменилось, покупает его, иначе он снова пропускает вперёд одного человека и звонит жене. При этом если после очередного звонка продавщица говорит, что товар закончился, покупатель выходит из очереди и отправляется домой ни с чем.
Марк очень хочет вернуться домой и наконец поужинать. Определите, сколько минут пройдёт перед тем, как он впервые окажется у прилавка. Один покупатель проводит у прилавка ровно одну минуту, телефонный разговор с женой длится полминуты.

Исходные данные

В первой строке записано целое число m (1 ≤ m ≤ 1000) — количество видов товаров, которыми торгует магазин. В каждой из следующих m строк описывается один товар. Описание товара имеет вид «amount of name», где name — название товара (непустая строка из строчных латинских букв длиной не более 20), а amount — количество единиц товара, которое имелось в наличии в тот момент, когда Марк зашёл в магазин (положительное целое число, не превосходящее 1000). Названия всех товаров различны.
В следующей строке записано целое число n (1 ≤ n ≤ 1000) — количество покупателей в очереди перед Марком. В каждой из следующих n строк описывается товар, который хочет купить очередной покупатель, в том же формате, в котором описаны товары в магазине. Покупатель мог прийти в магазин за товаром, который в этом магазине вообще не продаётся. Информация о покупателях дана в порядке от начала к концу очереди.

Результат

Выведите, сколько минут Марк простоит в очереди перед тем, как впервые подойдёт к прилавку.

Пример

исходные данныерезультат
3
2 of sweets
4 of milk
1 of sausage
4
2 of milk
3 of sweets
3 of milk
1 of cheese
6
Автор задачи: Андрей Гейн
Источник задачи: Уральская региональная командная олимпиада по программированию 2010
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1795. Мужья в магазине