Классифайд - 2

В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».

Вася открыл собственный классифайд (доску объявлений). Устроен его классифайд следующим образом: для каждого типа товара продавец с номером i i может выставить на продажу только одну единицу товара и заранее указывает минимальную цену S i S_i , за которую он готов его продать. Каждый покупатель может купить только одну единицу товара, покупатель с номером j j указывает максимальную цену B j B_j , за которую он готов купить товар. Раз в день Вася собирает все заявки и распределяет покупателей и продавцов, которые заключат сделку и по какой цене. При этом сделка между продавцом i i и покупателем j j может состояться только если S i B j S_i \le B_j по любой цене от S i S_i до B j B_j (цену назначает Вася).

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

Формат ввода

В первой строке задается число наборов тестовых данных T T . В этой задаче T T равно 10.

В первой строке описания каждого набора записано число N N ( 1 N 1000 1 \le N \le 1000 ) — количество продавцов.

В следующей строке записано N N чисел S i S_i ( 1 S i 1000 1 \le S_i \le 1000 ).

В следующей строке записано число M M ( 1 M 1000 1 \le M \le 1000 ).

В следующей строке записано M M чисел B i B_i ( 1 B i 1000 1 \le B_i \le 1000 ).

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

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

Для каждого набора входных данных выведите одно число — максимальную суммарную стоимость проданных товаров.

Система оценивания

Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).

Каждый набор тестовых данных оценивается в 5 баллов.