Автор: | Михалев Ю. | Ограничение времени: | 2 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход |
Вася играет в новую MMORPG и собирается пойти в рейд на босса. Однако, он столкнулся с двумя проблемами:
1. Он не знает на какого босса пойти
2. У него нет нужной экипировки для похода в рейд
Чтобы пойти в рейд на i-го босса, персонажу Васи нужно иметь уровней вещей персонажа не менее bi. Начальный уровень вещей персонажа Васи равен нулю. Вещи можно купить во внутриигровом магазине: j-ая вещь стоит aj монет и добавляет столько же к уровню вещей персонажа.
Каждую вещь для одного босса можно купить только один раз. Для разных боссов можно покупать одни и те же вещи. При этом Вася очень принципиальный и не хочет покупать вещь, если не были куплены все вещи меньшей стоимости. Иными словами, он хочет скупать только подряд идущие вещи, начиная с самой первой.
Вася попросил вас помочь ему с выбором и подсчитать минимальную стоимость экипировки, необходимой для похода в рейд на каждого босса
Первая строка входных данных содержит два целых числа: N — количество вещей в магазине и M — количество боссов.
Вторая строка содержит N чисел, отсортированных по возрастанию: ai — стоимость и уровень i-ой вещи в магазине.
Третья строка содержит M чисел: bi — минимальный уровень вещей, необходимый для похода в рейд на i-го босса
Выходные данные должны содержать M чисел: ci — минимальные затраты на покупку вещей для похода на i-го босса
В случае, если для данного босса невозможно получить необходимый уровень вещей, программа должна вывести -1
1 ≤ N ≤ 5 ⋅ 104
1 ≤ M ≤ 5 ⋅ 104
1 ≤ ai, bi ≤ 109
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|