Задание 26. Информатика. ЕГЭ. Основная волна. Пересдача. 03.07.2025

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из \(N\) участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков.

Для закупки доступно \(K\) моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.

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

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

Первая строка входного файла содержит два натуральных числа: \(N\) \((1 \leqslant N \leqslant 1~000~000)\) — количество участков СНТ и \(K\) \((1 \leqslant K \leqslant 100~000)\) — количество моделей снегоуборщиков соответственно. Следующие \(N\) строк содержат по одному натуральному числу, не превышающему \(1000,\) минимальные мощности снегоуборщиков, которые можно закупить для каждого из \(N\) участков. Далее в каждой из \(K\) строк содержится пара натуральных чисел — мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит \(1000,\) стоимость — \(100~000.\) Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно.

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

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

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

\(3 \, 4\)
\(1\)
\(2\)
\(3\)
\(10 \, 7\)
\(1 \, 5\)
\(3 \, 7\)
\(2 \, 3\)

При таких исходных данных для первого и второго участков оптимально закупить одинаковые снегоуборщики мощностью \(2\) и стоимостью \(3,\) для третьего участка будет закуплен снегоуборщик мощностью \(10.\) Стоимость закупки составит \(3 + 3 + 7 = 13.\) Ответ: \(13; \,\, 10.\)

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

fd = open('26.txt')
N, K = map(int, fd.readline().split())
wanted = []
for _ in range(N):
    wanted.append(int(fd.readline()))
price_power = {}
for _ in range(K):
    power, pr = map(int, fd.readline().split())
    price_power[pr] = max(power, price_power.get(pr, 0))

snow = [[0, 0] for _ in range(1001)]
snow[0] = [10**20, 10**20]
for price, power in sorted(list(price_power.items())):
    if not snow[power][1]:
        i = power
        while not snow[i][1]:
            snow[i] = [price, power]
            i -= 1
total_sum, max_pow = 0, 0
for power in wanted:
    total_sum += snow[power][0]
    max_pow = snow[power][1]
print(total_sum, max_pow)