Задание 26 ЕГЭ по информатике

В сеть детских технопарков поступила партия новых роботов. По инструкции каждому роботу рекомендована одна батарейка с достаточной емкостью для каждого робота. Все роботы пронумерованы последовательно от 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.

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/11921_26.txt