На складе вашего магазина находятся n пар обуви, каждая пара характеризуется двумя целыми числами: ценой ci и размером si. Известно, что именно в этот день все числа si различны, то есть каждого размера имеется не более одной пары.
В магазин зашли одновременно m покупателей, у покупателя номер i при себе di денег, а размер его ноги равен li. Покупатель номер i может купить себе пару номер j, если cj ≤ di, а также если li = sj или li = sj - 1; то есть необходимо, чтобы у него было достаточно денег чтобы заплатить, а также размер ноги был в точности равен или на 1 меньше, чем размер выбранной пары.
Ваша задача — продать некоторым покупателям по паре обуви так, чтобы максимизировать сумму cj проданных пар, то есть прибыль. Гарантируется, что каждый покупатель возьмет не более одной пары, а каждую пару, разумеется, купит не более одного покупателя.
Выходные данные
В первой строке выведите единственное целое число — максимальную прибыль, которую вы сможете получить от продажи. Во второй строке выведите целое число k — количество пар обуви, которые вы продадите. Далее в k строках выведите описания проданных пар — два целых числа через пробел, где первое число означает номер покупателя, а второе — номер обуви, которую этот покупатель приобретет.
Пары чисел «номер покупателя и номер обуви» можно выводить в любом порядке, покупатели и обувь нумеруются с 1 в том порядке, в котором они заданы во входных данных. Если существует несколько оптимальных ответов, то разрешается вывести любой.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 1
30 2
20 3
2
20 1
20 2
|
30
2
2 3
1 1
|
|
2
|
3
10 4
20 5
30 6
2
70 4
50 5
|
50
2
2 3
1 2
|