Задача D. Рейд на босса

Автор:Михалев Ю.   Ограничение времени: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
6 5
1 4 5 7 7 8
3 5 16 25 33
5 5 17 32 -1
2
10 8
10 20 30 40 50 60 70 80 90 100
1 2 9 10 550 551 151 150
10 10 10 10 550 -1 210 150

0.068s 0.008s 13