Задание выполняется с использованием прилагаемых файлов.
Производитель изготовил комплект санок для саночников, выступающих в парах. Все пары распределены на два потока. Входной файл содержит сведения о суммарной массе и номере потока каждого экипажа спортсменов (в граммах), грузоподъёмности санок (в граммах), среди которых менеджер команды будет выбирать подходящие. Экипаж может использовать санки, если суммарная масса спортсменов не превышает грузоподъёмности санок. Команды могут выбирать санки только таким образом, что сначала будут выступать максимально возможное количество пар с первого потока – а затем, любое количество пар со второго потока. Выступления саночников проходят в порядке возрастания вместимости их саней.
Определите максимальное количество экипажей спортсменов при таких правилах, для которых удастся выбрать санки, и суммарную массу спортсменов самого тяжёлого экипажа в этом случае.
Входные данные
В первой строке входного файла находятся два натуральных числа N (\(N \leq 100\,000\)) и M (\(M \leq 100\,000\)) – количество экипажей спортсменов и количество санок соответственно. Следующие N строк содержат числа, обозначающие суммарные массы экипажей и их номер потока, затем идут M строк, где указана грузоподъёмность санок. Числа M и N могут быть не равны. Гарантируется, что все санки имеют разную грузоподъёмность.
Запишите в ответе два натуральных числа: сначала максимальное количество экипажей, которые могут быть обеспечены санками, затем суммарную массу спортсменов самого тяжёлого экипажа в этом случае.