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