Обработка данных с сортировкой

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

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

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

Дан входной файл, который в первой строке содержит натуральное число N – количество новых роботов. Затем N строк содержащих целые числа c_i – минимальная емкость батарейки для робота с номером i. Затем следует натуральное число M – количество видов батареек, предоставленных для закупки. Далее в каждой из M строк содержится пара натуральных чисел a_i и b_i - емкость батарейки и ее цена соответственно.

Запишите в ответе два числа: минимальную сумму покупки батареек для всех роботов и стоимость самой дорогой батарейки, которая будет приобретена при оптимальной закупке.

Типовой пример организации файлов:

3

1

2

4

5

1 10

1 5

8 6

2 4

4 9

При таких исходных данных минимальная стоимость закупки будет составлять 14 (для первого и второго робота необходимо купить батарейки емкостью 2 и стоимостью 4, а для третьего робота емкостью 8 и стоимостью 6) 4 + 4 + 6 = 14. Цена самой дорогой купленной батарейки составит 6.