ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Тренировочный турнир сезона «Осень — 2018» > задача:


E. Макс и мины

Тренировочный турнир сезона «Осень — 2018»

Старт: 06.окт.2018 в 14:00:00
Финиш: 02.ноя.2018 в 23:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• A. Макс и Пасха
• B. Даниил и модульные весы
• C. Макс и RLE
• D. Макс и торрент
• E. Макс и мины
• F. Максимальное произведение
• G. Даниил и ряд врагов
• H. Даниил и составление расписания
• I. Даниил и пропавшие результаты
• J. Макс и Medieval
• P1. Таймер: Код доступа
• P10. Таймер: Упаковка конфет в к...
• P2. Таймер: Планирование процес...

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/6000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и мины
Макс и мины
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Максим — заядлый игрок в Dota 2, а его любимый герой — Минёр. Часто команда Максима страшно тупит, и тогда Максиму приходится спасать положение в одиночку.

Сегодня против Максима играют N персонажей, i-й из которых обладает здоровьем Ai и игнорирует Bi процентов любого наносимого урона.

Оружие Максима — мины, каждая из которых наносит при взрыве урон D всему живому. Максим устанавливает мины в M различных местах на карте, и в j-м из них он же разместил Cj мин.

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

Входные данные

Первая строка содержит целые числа N и D (1 ≤ N ≤ 105, 100 ≤ D ≤ 104) — соответственно количество противников и урон от взрыва мины.

Следующие N строк описывают противников. Каждая из них содержит целые числа Ai и Bi (100 ≤ Ai ≤ 105, 0 ≤ Bi ≤ 100)— соответственно здоровье i-го противника и процент игнорируемого им урона.

Следующая строка содержит целое число M (1 ≤ M ≤ 105) — количество заминированных мест.

Следующая строка содержит M целых чисел Cj (0 ≤ Cj ≤ 1000) — количества мин, установленных в каждом из выбранных мест.

Выходные данные

Выведите M целых чисел, j-е из которых равно количеству мин, которые нужно добавить в j-е место, чтобы лишить здоровья любого оказавшегося там героя.

Если Максим не сможет установить мины требуемым образом, выведите одно число -1.

Примеры тестов

Входные данные
5 200
500 25
250 50
1000 10
500 30
500 40
5
3 4 2 5 1
Выходные данные
3 2 4 1 5 
Входные данные
5 200
1000 5
750 25
1000 10
500 30
300 40
5
3 4 2 6 1
Выходные данные
3 2 4 0 5 
Для отправки решений необходимо выполнить вход.

www.contester.ru