G. Торговая задача
ограничение по времени на тест
4.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру (ага, опять). В этой игре довольно нестандартно реализована механика торговли.

Чтобы поторговать с кем-то из персонажей игры, Монокарп должен выбрать какую-то свою вещь и обменять ее на вещь того персонажа, с которым он торгует. У каждой вещи есть целочисленная цена. Если у Монокарпа есть вещь с ценой $$$x$$$, он может обменять ее на вещь (ровно одну) с ценой не более $$$x+k$$$.

Изначально у Монокарпа есть $$$n$$$ вещей, цена $$$i$$$-й из них равна $$$a_i$$$. У персонажа, с которым Монокарп торгует, изначально есть $$$m$$$ вещей, цена $$$i$$$-й из них равна $$$b_i$$$. Монокарп может поторговать с этим персонажем столько раз, сколько захочет (возможно, ноль), каждый раз меняя одну из своих вещей на вещь, принадлежащую персонажу, по описанным ранее правилам. Обратите внимание, что если Монокарп получает какую-то вещь в результате обмена, он потом может ее обменять на другую вещь (так как это теперь его вещь); и наоборот, если Монокарп отдал свою вещь в процессе обмена, он может получить ее обратно, обменяв на нее что-то еще.

Вы должны ответить на $$$q$$$ запросов. В каждом запросе вам подается одно целое число, которое соответствует значению $$$k$$$. Чтобы ответить на запрос, вы должны посчитать максимально возможную суммарную стоимость вещей, которые могут оказаться у Монокарпа (при условии, что вещь стоимости $$$x$$$ можно обменивать на вещь стоимости не более $$$x+k$$$). Обратите внимание, что запросы независимые: Монокарп на самом деле не обменивает вещи, он просто хочет оценить максимально возможную суммарную цену вещей.

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

В первой строке заданы три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1 \le n, m, q \le 2 \cdot 10^5$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — цены вещей, которые есть у Монокарпа.

В третьей строке заданы $$$m$$$ целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — цены вещей у персонажа, с которым торгует Монокарп.

В четвертой строке заданы $$$q$$$ целых чисел, $$$i$$$-е из которых равно значению $$$k$$$ в $$$i$$$-м запросе ($$$0 \le k \le 10^9$$$).

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

Для каждого запроса выведите одно целое число — максимально возможную суммарную цену вещей, которые могут оказаться у Монокарпа при заданном значении $$$k$$$ для запроса.

Пример
Входные данные
3 4 5
10 30 15
12 31 14 18
0 1 2 3 4
Выходные данные
55
56
60
64
64