D. Обувной магазин
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

На складе вашего магазина находятся n пар обуви, каждая пара характеризуется двумя целыми числами: ценой ci и размером si. Известно, что именно в этот день все числа si различны, то есть каждого размера имеется не более одной пары.

В магазин зашли одновременно m покупателей, у покупателя номер i при себе di денег, а размер его ноги равен li. Покупатель номер i может купить себе пару номер j, если cj ≤ di, а также если li = sj или li = sj - 1; то есть необходимо, чтобы у него было достаточно денег чтобы заплатить, а также размер ноги был в точности равен или на 1 меньше, чем размер выбранной пары.

Ваша задача — продать некоторым покупателям по паре обуви так, чтобы максимизировать сумму cj проданных пар, то есть прибыль. Гарантируется, что каждый покупатель возьмет не более одной пары, а каждую пару, разумеется, купит не более одного покупателя.

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

В первой строке входных данных записано единственное целое число n (1 ≤ n ≤ 105) — количество пар обуви на складе. Далее в n строках записаны описания пар обуви — два целых числа ci и si (1 ≤ ci, si ≤ 109), числа разделены пробелом. Гарантируется, что все числа si различны.

В следующей строке записано целое число m (1 ≤ m ≤ 105) — количество находящихся в магазине покупателей. Далее в m строках записаны описания покупателей — два целых числа di и li (1 ≤ di, li ≤ 109), числа разделены пробелом.

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

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

Пары чисел «номер покупателя и номер обуви» можно выводить в любом порядке, покупатели и обувь нумеруются с 1 в том порядке, в котором они заданы во входных данных. Если существует несколько оптимальных ответов, то разрешается вывести любой.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

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