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

Условие

Вася играет в новую MMORPG и собирается пойти в рейд на босса. Однако, он столкнулся с двумя проблемами:

1. Он не знает на какого босса пойти

2. У него нет нужной экипировки для похода в рейд

Чтобы пойти в рейд на i-го босса, персонажу Васи нужно иметь уровней вещей персонажа не менее b_i. Начальный уровень вещей персонажа Васи равен нулю. Вещи можно купить во внутриигровом магазине: j-ая вещь стоит a_j монет и добавляет столько же к уровню вещей персонажа.

Каждую вещь для одного босса можно купить только один раз. Для разных боссов можно покупать одни и те же вещи. При этом Вася очень принципиальный и не хочет покупать вещь, если не были куплены все вещи меньшей стоимости. Иными словами, он хочет скупать только подряд идущие вещи, начиная с самой первой.

Вася попросил вас помочь ему с выбором и подсчитать минимальную стоимость экипировки, необходимой для похода в рейд на каждого босса

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

Первая строка входных данных содержит два целых числа: N — количество вещей в магазине и M — количество боссов.

Вторая строка содержит N чисел, отсортированных по возрастанию: a_i  — стоимость и уровень i-ой вещи в магазине.

Третья строка содержит M чисел: b_i  — минимальный уровень вещей, необходимый для похода в рейд на i-го босса

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

Выходные данные должны содержать M чисел: c_i  — минимальные затраты на покупку вещей для похода на i-го босса

В случае, если для данного босса невозможно получить необходимый уровень вещей, программа должна вывести -1

Ограничения

1 ≤ N ≤ 5 ⋅ 10⁴

1 ≤ M ≤ 5 ⋅ 10⁴

1 ≤ a_i, b_i ≤ 10⁹

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

6 5
1 4 5 7 7 8
3 5 16 25 33

5 5 17 32 -1

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