C. Система бронирования
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Информационные технологии победоносно шагают по всей планете, проникая во все сферы человеческой деятельности!

Ресторан «У Дейкстры» задумался об автоматизации системы бронирования.

На сегодняшний вечер поступило n заявок от посетителей. Каждая заявка характеризуется двумя числами: ci и pi — размер группы посетителей, которая придет по этой заявке, и суммарное количество денег, которое они заплатят при посещении ресторана, соответственно.

Известно, что для каждой заявки все ci человек захотят сидеть за одним столиком и проведут в ресторане весь вечер от его открытия в 18:00 до закрытия.

К сожалению, в ресторане всего k столиков. Для каждого столика известно ri — максимальное количество человек, которые поместятся за этим столиком. За одним столиком могут сидеть только люди из одной группы. Если для удовлетворения заявки не хватает достаточно вместительного столика, то все посетители уходят и, естественно, ничего не платят.

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

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

В первой строке входных данных записано целое число n (1 ≤ n ≤ 1000) — количество заявок от посетителей. Далее следует n строк. Каждая строка содержит два целых числа: сi, pi (1 ≤ ci, pi ≤ 1000) — размер группы посетителей, которая придет по i-й заявке, и суммарное количество денег, которое они заплатят при посещении ресторана, соответственно.

В следующей строке записано целое число k (1 ≤ k ≤ 1000) — количество столиков в ресторане. В последней строке записано k целых чисел через пробел: r1, r2, ..., rk (1 ≤ ri ≤ 1000) — максимальное количество человек, которое можно разместить за каждым из столиков.

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

В первую строку выведите два числа: m, s — количество принятых заявок и суммарная прибыль, полученная от этих заявок, соответственно.

Далее выведите m строк — в каждой строке должно содержаться два целых числа, разделенных пробелом: номер принятой заявки и номер столика, за который стоит посадить людей, пришедших по этой заявке. Заявки и столики нумеруются последовательно начиная с 1 в порядке, в котором они заданы во входных данных.

Если существует несколько оптимальных ответов, разрешается вывести любой из них.

Примеры
Входные данные
3
10 50
2 100
5 30
3
4 6 9
Выходные данные
2 130
2 1
3 2