Innovation technologies are on a victorious march around the planet. They integrate into all spheres of human activity!

A restaurant called "Dijkstra's Place" has started thinking about optimizing the booking system. 

There are n booking requests received by now. Each request is characterized by two numbers: c_{i} and p_{i} — the size of the group of visitors who will come via this request and the total sum of money they will spend in the restaurant, correspondingly.

We know that for each request, all c_{i} people want to sit at the same table and are going to spend the whole evening in the restaurant, from the opening moment at 18:00 to the closing moment.

Unfortunately, there only are k tables in the restaurant. For each table, we know r_{i} — the maximum number of people who can sit at it. A table can have only people from the same group sitting at it. If you cannot find a large enough table for the whole group, then all visitors leave and naturally, pay nothing.

Your task is: given the tables and the requests, decide which requests to accept and which requests to decline so that the money paid by the happy and full visitors was maximum.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of requests from visitors. Then n lines follow. Each line contains two integers: c_{i}, p_{i} (1 ≤ c_{i}, p_{i} ≤ 1000) — the size of the group of visitors who will come by the i-th request and the total sum of money they will pay when they visit the restaurant, correspondingly.

The next line contains integer k (1 ≤ k ≤ 1000) — the number of tables in the restaurant. The last line contains k space-separated integers: r_1, r_2, ..., r_{k} (1 ≤ r_{i} ≤ 1000) — the maximum number of people that can sit at each table.


-----Output-----

In the first line print two integers: m, s — the number of accepted requests and the total money you get from these requests, correspondingly.

Then print m lines — each line must contain two space-separated integers: the number of the accepted request and the number of the table to seat people who come via this request. The requests and the tables are consecutively numbered starting from 1 in the order in which they are given in the input.

If there are multiple optimal answers, print any of them.


-----Examples-----
Input
3
10 50
2 100
5 30
3
4 6 9

Output
2 130
2 1
3 2

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Implementation

Greedy algorithms
Skill types: Dynamic programming

Sorting

Greedy algorithms

Starter code:

Solutions:
n = int(input())
x = []
for i in range(n):
	(c, p) = map(int, input().split())
	x += [(p, c, i)]
k = int(input())
r = list(map(int, input().split()))
s = 0
q = []
for (v, c, a) in reversed(sorted(x)):
	p = -1
	u = 100000
	for (j, z) in enumerate(r):
		if c <= z < u:
			p = j
			u = z
	if p > -1:
		r[p] = 0
		q += [(a, p)]
		s += v
print(len(q), s)
for (i, j) in q:
	print(i + 1, j + 1)


n = int(input())

class req:

	def __init__(self, no, size, cash):
		self.no = no
		self.size = size
		self.cash = cash

class table:

	def __init__(self, no, size):
		self.no = no
		self.size = size
rl = []
for i in range(n):
	(s, c) = [int(x) for x in input().split()]
	a = req(i + 1, s, c)
	rl.append(a)
k = int(input())
t = [int(x) for x in input().split()]
tl = []
for i in range(len(t)):
	a = table(i + 1, t[i])
	tl.append(a)
rl.sort(key=lambda x: x.cash, reverse=True)
tl.sort(key=lambda x: x.size)
tot = 0
seated = 0
a = []
for i in tl:
	s = i.size
	for j in rl:
		if j.size <= i.size:
			tot += j.cash
			seated += 1
			a.append([j.no, i.no])
			rl.remove(j)
			break
a.sort(key=lambda x: x[0])
print(seated, tot)
for i in a:
	print(i[0], i[1])


import sys
from math import log2, floor, ceil, sqrt
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
n = int(ri())
vis = []
for i in range(n):
	(c, p) = Ri()
	vis.append([c, p, i])
t = int(ri())
r = Ri()
r = [[r[i], i] for i in range(t)]
r.sort(key=lambda x: x[0])
vis.sort(key=lambda x: (x[1], -x[0]), reverse=True)
ans = 0
flag = [True] * t
tcus = []
for i in range(n):
	tf = -1
	cus = vis[i]
	for j in range(t):
		if cus[0] <= r[j][0] and flag[j]:
			tf = j
			break
	if tf != -1:
		flag[tf] = False
		ans += cus[1]
		tcus.append([i, tf])
print(len(tcus), ans)
for i in range(len(tcus)):
	cus = tcus[i][0]
	t = tcus[i][1]
	print(vis[cus][2] + 1, r[t][1] + 1)


n = int(input())
q = []
for i in range(n):
	(x, y) = map(int, input().split())
	q.append((y, x, i + 1))
m = int(input())
t = list(map(int, input().split()))
t = list(enumerate(t, 1))
t = list(map(lambda x: [x[1], x[0]], t))
q.sort()
t.sort()
(res, sum) = ([], 0)
for i in range(n - 1, -1, -1):
	for j in range(m):
		if q[i][1] <= t[j][0]:
			t[j][0] = 0
			sum += q[i][0]
			res.append((q[i][2], t[j][1]))
			break
print(len(res), sum)
for i in res:
	print(*i)


n = int(input())
requests = []
i = 0
while i != n:
	(c, p) = [int(x) for x in input().split()]
	requests.append((p, c, i + 1))
	i += 1
k = int(input())
R = input().split()
r = []
for x in range(len(R)):
	r.append((int(R[x]), x + 1))
m = s = 0
accepted = []
maxx = (0, 0, 0)
reverse_sorted_requests = list(reversed(sorted(requests)))
for j in sorted(r):
	for i in reverse_sorted_requests:
		if maxx[2] == 0 and i[1] <= j[0]:
			maxx = i
		elif i[0] > maxx[0] and i[1] <= j[0]:
			maxx = i
	if maxx[2] != 0:
		accepted.append((maxx[2], j[1]))
		m += 1
		s += maxx[0]
		reverse_sorted_requests.remove(maxx)
		maxx = (0, 0, 0)
print(m, s)
for a in accepted:
	print(a[0], a[1])


import sys
input = sys.stdin.readline
read_tuple = lambda _type: map(_type, input().split(' '))

def solve():
	n = int(input())
	c_p = []
	for i in range(n):
		(c_i, p_i) = read_tuple(int)
		c_p.append((c_i, p_i, i + 1))
	k = int(input())
	r = [(r_i, i + 1) for (i, r_i) in enumerate(read_tuple(int))]
	c_p.sort(key=lambda x: x[1])
	r.sort(key=lambda x: x[0])
	m = 0
	s = 0
	info = []
	while c_p and r:
		(c_i, p_i, i) = c_p[-1]
		if c_i > r[-1][0]:
			c_p.pop()
		else:
			idx = 0
			(r_j, j) = r[idx]
			while r_j < c_i:
				idx += 1
				(r_j, j) = r[idx]
			m += 1
			s += p_i
			info.append((i, j))
			c_p.pop()
			r.pop(idx)
	print(m, s)
	for (i, j) in sorted(info):
		print(i, j)
solve()


n = int(input())
arr = []
for i in range(n):
	arr.append(list(map(int, input().strip().split())) + [i + 1])
k = int(input())
tables = list(map(int, input().strip().split()))
arr.sort(key=lambda x: -x[1])
ans = []
vis = [0 for i in range(k)]
for i in arr:
	mini = float('inf')
	temp = None
	for j in range(k):
		if vis[j] == 0 and tables[j] >= i[0] and (tables[j] < mini):
			temp = i + [j + 1]
			mini = tables[j]
	if temp:
		vis[temp[-1] - 1] = 1
		ans.append(temp)
tot = 0
for i in ans:
	tot += i[1]
print(len(ans), tot)
for i in ans:
	print(*i[-2:])


n = int(input())
cp = [list(map(int, input().split())) + [i] for i in range(n)]
k = int(input())
r = list(map(int, input().split()))
for i in range(k):
	r[i] = [r[i], i]
cp.sort(key=lambda x: x[1], reverse=True)
r.sort()
use = [False] * k
ans = []
(m, s) = (0, 0)
for i in range(n):
	(c, p, idx) = cp[i]
	for j in range(k):
		(rr, idx2) = r[j]
		if rr >= c and (not use[j]):
			use[j] = True
			m += 1
			s += p
			ans.append([idx + 1, idx2 + 1])
			break
print(m, s)
for x in ans:
	print(*x)


from sys import stdin
from bisect import *
from collections import *

def get_col(arr, i):
	return [row[i] for row in arr]

def arr_2d(n):
	return [[i + 1, [int(x) for x in stdin.readline().split()]] for i in range(n)]

def arr_inp_enu(n):
	return [[i + 1, int(x)] for (i, x) in enumerate(stdin.readline().split())]
(n, ans, out) = (int(input()), [0, 0], [])
(req, k) = (sorted(arr_2d(n), key=lambda x: x[1][1], reverse=True), int(input()))
table = sorted(arr_inp_enu(k), key=lambda x: x[1])
(col, mem) = (get_col(table, 1), defaultdict(deque))
for i in range(k):
	mem[col[i]].append(table[i][0])
for i in range(n):
	if table:
		ix = bisect_right(col, req[i][1][0])
		if ix > 0 and col[ix - 1] == req[i][1][0]:
			ix -= 1
		if ix < len(col):
			ans[0] += 1
			ans[1] += req[i][1][1]
			out.append([req[i][0], mem[col[ix]][0]])
			mem[col[ix]].popleft()
			col.pop(ix)
	else:
		break
print(*ans)
for i in range(ans[0]):
	print(*out[i])


import math
import random

def main(arr, tables):
	idx_arr = {}
	for i in range(len(arr)):
		val = arr[i]
		if val not in idx_arr:
			idx_arr[val] = []
		idx_arr[val].append(i + 1)
	table_arr = {}
	for i in range(len(tables)):
		val = tables[i]
		if val not in table_arr:
			table_arr[val] = []
		table_arr[val].append(i + 1)
	arr.sort(key=lambda x: x[1], reverse=True)
	tot = 0
	ans = []
	for i in range(len(arr)):
		(p, c) = arr[i]
		val = float('inf')
		idx_for_table = None
		for j in range(len(tables)):
			if tables[j] >= p:
				if val > tables[j]:
					val = tables[j]
					idx_for_table = j + 1
		if val != float('inf'):
			ans.append([idx_arr[p, c][-1], idx_for_table])
			idx_arr[p, c].pop()
			tables[idx_for_table - 1] = 0
			tot += c
	print(len(ans), tot)
	for e in ans:
		print(*e)
n = int(input())
arr = []
for i in range(n):
	arr.append(tuple(map(int, input().split())))
m = int(input())
tables = list(map(int, input().split()))
main(arr, tables)


from bisect import bisect
number_of_requests = int(input())
group_size_and_money = []
for i in range(number_of_requests):
	(group_size, money) = map(int, input().strip().split(' '))
	group_size_and_money.append((group_size, money, i))
group_size_and_money.sort(key=lambda x: x[1], reverse=True)
number_of_tables = int(input())
list_tables = list(map(int, input().strip().split(' ')))
tables_and_index = []
for (index, value) in enumerate(list_tables):
	tables_and_index.append((value, index))
tables_and_index.sort(key=lambda x: x[0])
final_value = []
final_money = 0
for element in group_size_and_money:
	looking_table = bisect(tables_and_index, (element[0], -1))
	if looking_table < len(tables_and_index):
		(table, index) = tables_and_index.pop(looking_table)
		final_value.append((element[2] + 1, index + 1))
		final_money += element[1]
	elif tables_and_index and looking_table == len(tables_and_index) and (element[0] == tables_and_index[-1][0]):
		(table, index) = tables_and_index.pop()
		final_value.append((element[2] + 1, index + 1))
		final_money += element[1]
print(len(final_value), final_money)
for (request_number, request_table) in final_value:
	print(request_number, request_table)


import bisect
n = int(input())
vs = list(enumerate([tuple(map(int, input().split(' '))) for _ in range(n)]))
k = int(input())
rs = list(map(int, input().split(' ')))
rs_i = {r: [i + 1 for (i, k) in enumerate(rs) if k == r] for r in rs}
vs.sort(key=lambda x: x[1][1])
rs.sort()
ol_rs = len(rs)
(s, ss) = (0, list())
while len(vs) > 0:
	(i, (c, p)) = vs.pop()
	t = bisect.bisect_left(rs, c)
	if t < len(rs):
		s += p
		ss.append((i + 1, rs_i[rs[t]].pop()))
		del rs[t]
print('{} {}'.format(ol_rs - len(rs), s))
for tt in ss:
	print('{} {}'.format(*tt))


n = int(input())
g = [list(map(int, input().split())) + [i] for i in range(n)]
k = int(input())
r = [(v, i) for (i, v) in enumerate(list(map(int, input().split())))]
b = [None] * n
sg = sorted(g, key=lambda x: x[1], reverse=True)
sr = sorted(r)
count = 0
money = 0
for v in sg:
	for w in sr:
		if w[0] < v[0]:
			continue
		b[v[2]] = w[1]
		count += 1
		money += v[1]
		sr.remove(w)
		break
print(count, money)
for i in range(n):
	if b[i] == None:
		continue
	print(i + 1, b[i] + 1)


import bisect, sys
input = sys.stdin.readline

def binary_search(array, value, l=0, h=None):
	array = [i[0] for i in array]
	if not h:
		h = len(array)
	index = bisect.bisect_left(array, value, l, h)
	if index != h and array[index] >= value:
		return index
	else:
		return -1
people = [[int(i) for i in input().split()] + [j] for j in range(int(input()))]
(k, tables) = (int(input()), [int(i) for i in input().split()])
(tables, money, accepted_num, accepted) = ([[tables[i]] + [i] for i in range(k)], 0, 0, [])
people.sort(key=lambda x: x[1], reverse=True)
tables.sort(key=lambda x: x[0])
for i in range(len(people)):
	ree = binary_search(tables, people[i][0])
	if ree != -1:
		accepted_num += 1
		money += people[i][1]
		accepted.append([people[i][2] + 1, tables[ree][1] + 1])
		del tables[ree]
print(accepted_num, money)
for i in range(len(accepted)):
	print(*accepted[i])


n = int(input())
x = []
for i in range(n):
	(c, p) = map(int, input().split())
	x += [(p, c, i)]
k = int(input())
r = list(map(int, input().split()))
sm = 0
ans = []
x.sort(reverse=True)
for i in range(n):
	count = x[i][0]
	cost = x[i][1]
	uk = x[i][2]
	tm1 = -1
	tm2 = 100000
	for j in range(k):
		if cost <= r[j] < tm2:
			tm1 = j
			tm2 = r[j]
	if tm1 > -1:
		r[tm1] = 0
		ans += [(uk, tm1)]
		sm += count
print(len(ans), sm)
for (i, j) in ans:
	print(i + 1, j + 1)


import math
arr = []
cap = []
w = int(input())
for _ in range(w):
	(o, p) = map(int, input().split())
	arr += [[p, o, _ + 1]]
h = int(input())
cap = list(map(int, input().split()))
capArr = []
for _ in range(h):
	capArr += [[cap[_], _ + 1, -1]]
arr.sort(reverse=True)
capArr.sort()
ans = []
sum = 0
for itr in arr:
	tar = itr[1]
	for qr in capArr:
		if qr[2] == -1 and qr[0] - tar >= 0:
			qr[2] = itr[2]
			sum += itr[0]
			ans += [qr]
			break
print(len(ans), sum)
for itr in ans:
	print(itr[2], itr[1])


from bisect import bisect_right
R = lambda : map(int, input().split())
n = int(input())
reqs = []
for i in range(n):
	(num, c) = R()
	reqs.append((num, c, i))
t = int(input())
tables = sorted(((table, i) for (i, table) in enumerate(R())))
reqs.sort(key=lambda x: (-x[1], x[0]))
(sol, tc) = (dict(), 0)
for r in reqs:
	i = bisect_right(tables, (r[0], -1))
	if i < len(tables):
		sol[r[2]] = tables[i][1]
		tc += r[1]
		tables = tables[:i] + tables[i + 1:]
print(len(sol), tc)
for k in sol.keys():
	print(k + 1, sol[k] + 1)


from collections import namedtuple
n = int(input())
Table = namedtuple('Table', 'id, size')
Group = namedtuple('Group', 'id, size, income')

def first_fit(size):
	for t in tables:
		if t.size >= size and t.id not in used_tables:
			used_tables.add(t.id)
			return t
(tables, groups) = ([], [])
used_tables = set()
for i in range(n):
	(c, p) = list(map(int, input().split()))
	groups.append(Group(i + 1, c, p))
k = int(input())
r = list(map(int, input().split()))
for i in range(k):
	tables.append(Table(i + 1, r[i]))
groups.sort(key=lambda group: group.income, reverse=True)
tables.sort(key=lambda table: table.size)
sum_ = 0
ans = []
for i in range(n):
	g = groups[i]
	needed_table = first_fit(g.size)
	if not needed_table:
		continue
	sum_ += g.income
	ans.append((g.id, needed_table.id))
print(len(ans), sum_)
for a in ans:
	print(*a)


from heapq import *
pq = []
ans = []
a = int(input())
for i in range(a):
	(x, y) = map(int, input().split())
	ans.append([x, y, i + 1])
temp = ans.copy()
ans.sort()
s = int(input())
z = list(map(int, input().split()))
t1 = []
for i in range(len(z)):
	t1.append([z[i], i + 1])
t1.sort()
fin = []
cnt = 0
total = 0
for i in range(len(t1)):
	while cnt < len(ans) and ans[cnt][0] <= t1[i][0]:
		heappush(pq, (-ans[cnt][1], ans[cnt][2]))
		cnt += 1
	if len(pq):
		r = heappop(pq)
		fin.append([r[1], t1[i][1]])
		total += temp[r[1] - 1][1]
print(len(fin), total)
for i in range(len(fin)):
	print(fin[i][0], fin[i][1])


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	n = int(input())
	arr = []
	d1 = defaultdict(list)
	d2 = defaultdict(list)
	for i in range(1, n + 1):
		(c, p) = map(int, input().split())
		d1[c, p].append(i)
		arr.append((c, p))
	k = int(input())
	r = list(map(int, input().split()))
	for i in range(1, k + 1):
		d2[r[i - 1]].append(i)
	r = SortedList(r)
	arr.sort(key=lambda x: -x[1])
	l = 0
	ans = []
	sm = 0
	while l < n and len(r):
		c = arr[l][0]
		z = r.bisect_left(c)
		if z == len(r):
			l += 1
			continue
		sm += arr[l][1]
		ans.append((d1[arr[l]].pop(), d2[r[z]].pop()))
		r.remove(r[z])
		l += 1
	print(len(ans), sm)
	for _ in ans:
		print(*_)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import string
import math
from collections import defaultdict
from functools import lru_cache
from collections import Counter
from fractions import Fraction

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def jsns(lst):
	return ''.join((str(d) for d in lst))

def line():
	return sys.stdin.readline().strip()

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))

def main():
	n = iline()
	requests = []
	for _ in range(n):
		requests.append(tmi(line()))
	line()
	tables = list(enumerate(lmi(line())))
	tables.sort(key=lambda x: x[1])
	max_size = tables[-1][1]
	requests = [(e + 1, request[0], request[1]) for (e, request) in enumerate(requests) if request[0] <= max_size]
	requests.sort(key=lambda x: x[2], reverse=True)
	total = 0
	used = []
	for (number, size, money) in requests:
		for (e, tab_data) in enumerate(tables):
			(tab_num, tab_size) = tab_data
			if tab_size is not None and tab_size >= size:
				tables[e] = (tab_num, None)
				total += money
				used.append((number, tab_num + 1))
				break
	print(len(used), total)
	for (num, tab_num) in used:
		print(num, tab_num)
main()


n = int(input())
R = []
for r in range(n):
	(c, p) = list(map(int, input().split()))
	R.append((p, c, r + 1))
m = int(input())
T = list(map(int, input().split()))
T = sorted([[c, i + 1] for (i, c) in enumerate(T)])
R = sorted(R, reverse=True)
ans = 0
B = []
for (p, c, r) in R:
	for i in range(m):
		if T[i][0] >= c:
			B.append((r, T[i][1]))
			T[i][0] = -1
			ans += p
			break
print(len(B), ans)
for (r, t) in B:
	print(r, t)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left as bl
from collections import defaultdict
n = int(input())
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
d = defaultdict(list)
for i in range(n - 1, -1, -1):
	d[l[i][0], l[i][1]].append(i + 1)
k = int(input())
l1 = list(map(int, input().split()))
l2 = []
for i in range(k):
	l2.append([l1[i], i])
l2.sort()
l.sort()
ans1 = 0
ans2 = 0
ans = []
for i in range(k):
	if len(l) == 0:
		break
	a = bl(l, [l2[i][0], 1001])
	x = 0
	y = 0
	for j in range(a):
		if x <= l[j][1]:
			x = l[j][1]
			y = j
	if x:
		ans1 += 1
		ans2 += x
		ans.append([d[l[y][0], l[y][1]][-1], l2[i][1] + 1])
		d[l[y][0], l[y][1]].pop()
		l.pop(y)
print(ans1, ans2)
ans.sort()
for i in ans:
	print(*i)


import sys

def bin_search(c, k, rs):
	(l, r) = (0, k)
	while l < r:
		mid = (l + r) // 2
		if c == rs[mid][0]:
			return mid
		if c < rs[mid][0]:
			r = mid
		else:
			l = mid + 1
	return l

def solve(n, groups, k, rs):
	groups.sort(key=lambda x: (-x[2], x[1]))
	seated = [False for _ in rs]
	rs = sorted([(r, i + 1) for (i, r) in enumerate(rs)], key=lambda x: x[0])
	res = []
	total = 0
	for (m, c, p) in groups:
		index = bin_search(c, k, rs)
		while 0 < index and index < k and (rs[index - 1][0] == rs[index][0]):
			index -= 1
		while index < k and seated[index]:
			index += 1
		if index < k:
			res.append((m, rs[index][1]))
			total += p
			seated[index] = True
	print('{} {}'.format(len(res), total))
	for (m, i) in res:
		print('{} {}'.format(m, i))

def main():
	n = int(input())
	groups = []
	for i in range(n):
		(c, p) = map(int, input().split())
		groups.append((i + 1, c, p))
	k = int(input())
	rs = list(map(int, input().split()))
	solve(n, groups, k, rs)
main()


n = int(input())
P = []
for i in range(n):
	(x, y) = map(int, input().split())
	P.append((y, x, i))
k = int(input())
L = list(map(int, input().split()))
for i in range(k):
	L[i] = (L[i], i)
L.sort()
P.sort(reverse=True)
ans = 0
Taken = [False] * k
r = 0
Ans = [-1] * n
for i in range(n):
	for j in range(k):
		if L[j][0] >= P[i][1] and Taken[j] == False:
			Taken[j] = True
			ans += P[i][0]
			r += 1
			Ans[P[i][2]] = L[j][1]
			break
print(r, ans)
for i in range(n):
	if Ans[i] == -1:
		continue
	print(i + 1, Ans[i] + 1)


import sys
input = sys.stdin.readline

def multi_input():
	return map(int, input().split())

def array_print(arr):
	print(' '.join(map(str, arr)))
requests = []
r = int(input())
for n in range(1, r + 1):
	(p, c) = multi_input()
	requests.append([n, p, c])
t = int(input())
tables = list(multi_input())
tables_index = [0] * t
requests.sort(key=lambda item: item[2], reverse=True)
ans = []
profit = 0
for i in range(r):
	req_index = requests[i][0]
	person = requests[i][1]
	cost = requests[i][2]
	idx = -1
	jgte = 1000000
	for j in range(t):
		if tables_index[j] == 0 and tables[j] >= person and (jgte >= tables[j]):
			jgte = tables[j]
			idx = j
	if idx != -1:
		profit += cost
		tables_index[idx] = 1
		ans.append([req_index, idx + 1])
print(len(ans), profit)
for i in range(len(ans)):
	print(ans[i][0], ans[i][1])


import math, sys
from sys import stdin, stdout
from collections import Counter, defaultdict, deque
input = stdin.readline
I = lambda : int(input())
li = lambda : list(map(int, input().split()))

def search(key, table, l, r, p):
	if l > r:
		return p
	mid = (l + r) // 2
	if table[mid][0] == key:
		p = mid
	elif table[mid][0] > key:
		p = mid
		p = search(key, table, l, mid - 1, p)
	else:
		p = search(key, table, mid + 1, r, p)
	return p

def case():
	n = I()
	a = []
	for i in range(n):
		(p, q) = li()
		a.append([q, p, i])
	a.sort(reverse=True)
	m = I()
	table = li()
	for i in range(m):
		table[i] = [table[i], i]
	table.sort()
	pink = []
	ans = 0
	for i in range(n):
		k = search(a[i][1], table, 0, len(table) - 1, -1)
		if k == -1:
			continue
		ans += a[i][0]
		pink.append([a[i][2] + 1, table[k][1] + 1])
		del table[k]
	print(len(pink), ans)
	for i in pink:
		print(*i)
for _ in range(1):
	case()


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
req = {}
for i in range(n):
	r = value()
	req[i + 1] = r
req = {k: v for (k, v) in sorted(req.items(), key=lambda item: item[1][1], reverse=True)}
tab = {}
t = Int()
a = array()
for _ in range(t):
	tab[_ + 1] = a[_]
tab = {k: v for (k, v) in sorted(tab.items(), key=lambda item: item[1])}
total = 0
flag = defaultdict(bool)
ans = []
for r in req:
	mem = req[r][0]
	mon = req[r][1]
	for t in tab:
		if tab[t] >= mem and (not flag[t]):
			total += mon
			ans.append((r, t))
			flag[t] = True
			break
print(len(ans), total)
for i in ans:
	print(*i)


from sys import stdin
input = stdin.readline

class Booking:

	def __init__(self, number, people, cost):
		self.number = number
		self.people = people
		self.cost = cost
		self.table = None

	def __str__(self):
		return str(self.__dict__)

class Table:

	def __init__(self, number, capacity):
		self.number = number
		self.capacity = capacity
		self.occupied = False

	def __str__(self):
		return str(self.__dict__)
b = int(input())
requests = [[int(item) for item in input().split(' ')] for i in range(b)]
bookings = []
for i in range(b):
	bookings.append(Booking(i + 1, requests[i][0], requests[i][1]))
n = int(input())
capacity = [int(item) for item in input().split(' ')]
tables = []
for i in range(n):
	tables.append(Table(i + 1, capacity[i]))
st = [table for table in sorted(tables, key=lambda x: x.capacity)]
granted = 0
total = 0
for booking in sorted(bookings, key=lambda bo: -1 * bo.cost):
	if granted == len(st):
		break
	for table in st:
		if table.occupied:
			continue
		if table.capacity >= booking.people:
			booking.table = table.number
			total += booking.cost
			table.occupied = True
			granted += 1
			break
print(granted, total)
for booking in bookings:
	if booking.table:
		print(booking.number, booking.table)


n = int(input())
clients = []
for i in range(1, n + 1):
	clients.append(list(map(int, input().split())))
	clients[-1].reverse()
	clients[-1] += [i]
k = int(input())
r = list(map(int, input().split()))
s = 0
answer = []
clients.sort(reverse=True)
r = [1001] + r
for i in clients:
	pos = 0
	for j in range(k + 1):
		if r[j] >= i[1] and r[j] < r[pos]:
			pos = j
	if r[pos] >= i[1] and pos:
		answer.append(str(i[2]) + ' ' + str(pos))
		r[pos] = 0
		s += i[0]
print(len(answer), s)
print('\n'.join(answer))


def get_key(item):
	return item[1]
n = int(input())
requests = []
for i in range(n):
	(c, p) = map(int, input().split())
	requests.append([c, p, i + 1])
k = int(input())
l = list(map(int, input().split()))
capacity = []
for i in range(k):
	capacity.append([l[i], i + 1, 0])
capacity = sorted(capacity)
requests = sorted(requests, key=get_key, reverse=True)
results = []
sum = 0
for i in range(n):
	for j in range(k):
		if capacity[j][2] == 0 and requests[i][0] <= capacity[j][0]:
			capacity[j][2] = 1
			results.append([requests[i][2], capacity[j][1]])
			sum += requests[i][1]
			break
print(len(results), sum)
for i in results:
	print(i[0], i[1])


from bisect import bisect_left
n = int(input())
a = [0] * n
for i in range(n):
	(c, p) = map(int, input().split())
	a[i] = (p, c, i + 1)
a.sort(reverse=True)
m = int(input())
b = [0] * m
for (j, r) in enumerate(map(int, input().split())):
	b[j] = (r, j + 1)
b.sort()
(s, q) = (0, [])
for (p, c, i) in a:
	k = bisect_left(b, (c, 0))
	if k == len(b):
		continue
	(r, j) = b.pop(k)
	q.append(str(i) + ' ' + str(j))
	s += p
	if not b:
		break
print(len(q), s)
print('\n'.join(q))


from _collections import defaultdict
n = int(input())
d = defaultdict(list)
for i in range(1, n + 1):
	d[tuple(map(int, input().split()))].append(i)
m = int(input())
t = defaultdict(list)
for (x, y) in enumerate(map(int, input().split()), 1):
	t[y].append(x)
s = 0
c = 0
l = []
for x in sorted(d.keys(), key=lambda x: (-x[1], x[0])):
	for j in d[x]:
		for i in sorted(t):
			if len(t[i]) > 0 and i >= x[0]:
				z = 0
				for v in t[i]:
					s += x[1]
					c += 1
					l.append([j, v])
					t[i].pop(t[i].index(v))
					n += 1
					z = 1
					break
				if len(t[i]) == 0:
					del t[i]
				if z == 1:
					break
print(c, s)
for i in l:
	print(*i)


import math
import random

def main(arr, tables):
	idx_arr = {}
	for i in range(len(arr)):
		val = arr[i]
		if val not in idx_arr:
			idx_arr[val] = []
		idx_arr[val].append(i + 1)
	table_arr = {}
	for i in range(len(tables)):
		val = tables[i]
		if val not in table_arr:
			table_arr[val] = []
		table_arr[val].append(i + 1)
	arr.sort(key=lambda x: x[1], reverse=True)
	tot = 0
	ans = []
	tables.sort()
	for i in range(len(arr)):
		(p, c) = arr[i]
		if len(tables) == 0:
			break
		l = 0
		r = len(tables) - 1
		found = False
		while l < r:
			m = (l + r) // 2
			if tables[m] == p:
				ans.append([idx_arr[p, c][-1], table_arr[tables[m]][-1]])
				idx_arr[p, c].pop()
				table_arr[tables[m]].pop()
				tables.pop(m)
				found = True
				tot += c
				break
			elif tables[m] < p:
				l = m + 1
			else:
				r = m
		if not found:
			val = tables[r]
			if val >= p:
				ans.append([idx_arr[p, c][-1], table_arr[tables[r]][-1]])
				idx_arr[p, c].pop()
				table_arr[tables[r]].pop()
				tables.pop(r)
				found = True
				tot += c
	print(len(ans), tot)
	for e in ans:
		print(*e)
	return
n = int(input())
arr = []
for i in range(n):
	arr.append(tuple(map(int, input().split())))
m = int(input())
tables = list(map(int, input().split()))
main(arr, tables)


from bisect import bisect_left as lower

def put():
	return map(int, input().split())
n = int(input())
(c, p) = ([], [])
for i in range(n):
	(ci, pi) = put()
	c.append(ci)
	p.append(pi)
k = int(input())
rr = list(put())
l = []
for i in range(n):
	l.append((p[i], c[i], i + 1))
l.sort()
r = []
for (i, v) in enumerate(rr):
	r.append((v, i + 1))
r.sort()
t = k
(x, y) = (0, 0)
vis = [0] * k
ans = []
while t > 0 and l:
	(p, c, a) = l.pop()
	j = lower(r, (c, 0))
	while j < k and vis[j]:
		j += 1
	if j < k:
		x += 1
		y += p
		vis[j] = 1
		t -= 1
		ans.append((a, r[j][1]))
print(x, y)
for (a, b) in ans:
	print(a, b)


import heapq
n = int(input())
req = []
for i in range(n):
	(c, p) = map(int, input().split())
	req.append((c, p, i + 1))
req.sort()
x = int(input())
r1 = list(map(int, input().split()))
r = []
for i in range(x):
	r.append((r1[i], i + 1))
r.sort()
l1 = []
z = 0
ans = 0
anslist = []
for i in range(x):
	while z < n and req[z][0] <= r[i][0]:
		heapq.heappush(l1, (-req[z][1], req[z][2]))
		z += 1
	if len(l1) > 0:
		f = l1[0]
		ans -= f[0]
		heapq.heappop(l1)
		anslist.append(str(f[1]) + ' ' + str(r[i][1]))
print(len(anslist), ans)
print('\n'.join(anslist))


def findTable(tables, c, visited):
	min_diff = float('inf')
	index = -1
	k = len(tables)
	for i in range(k):
		diff = tables[i] - c
		if diff >= 0:
			if diff < min_diff and i + 1 not in visited:
				min_diff = diff
				index = i + 1
	if index != -1:
		visited.add(index)
	return index

def main():
	n = int(input())
	visitors = []
	for i in range(n):
		(c, p) = map(int, input().split())
		visitors.append((p, c, i + 1))
	visitors.sort(reverse=True)
	ans = []
	money = 0
	k = int(input())
	tables = list(map(int, input().split()))
	visited = set()
	for visitor in visitors:
		(p, c) = (visitor[0], visitor[1])
		index = findTable(tables, c, visited)
		if index != -1:
			visited.add(index)
			ans.append((visitor[2], index))
			money += p
	print(len(ans), money)
	for i in ans:
		print(i[0], i[1])
main()


import bisect
from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	n = ii()
	a = []
	for i in range(n):
		(c, p) = mii()
		a.append([c, p, i + 1])
	a.sort(key=lambda x: x[1], reverse=True)
	check = defaultdict(int)
	k = ii()
	ch = lmii()
	pp = list(ch)
	sm = 0
	ch.sort()
	ans = []
	for i in range(n):
		pos = bisect.bisect_left(ch, a[i][0])
		if pos != len(ch):
			sm += a[i][1]
			for j in range(k):
				if pp[j] == ch[pos] and check[j] == 0:
					check[j] = 1
					ans.append([a[i][2], j + 1])
					ch.pop(pos)
					break
	print(len(ans), sm)
	for i in range(len(ans)):
		print(*ans[i])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import bisect

def ans(n, k):
	if dp[n][k] != -1:
		return dp[n][k]
	if k == 0 and n != 0:
		return ans(n - 1, k)
	if n == 0:
		return 0
	if l[n - 1][0] <= lll[k - 1]:
		dp[n][k] = max(l[n - 1][1] + ans(n - 1, k - 1), ans(n - 1, k), ans(n, k - 1))
		return max(l[n - 1][1] + ans(n - 1, k - 1), ans(n - 1, k), ans(n, k - 1))
	else:
		dp[n][k] = max(ans(n - 1, k), ans(n, k - 1))
		return max(ans(n - 1, k), ans(n, k - 1))
n = int(input())
l = []
ll = []
for i in range(n):
	l1 = list(map(int, input().split()))
	l1.append(i)
	l.append(l1)
k = int(input())
lll = list(map(int, input().split()))
dp = []
l1 = []
l2 = []
ans = []
count = 0
l2 = sorted(lll)
l.sort(key=lambda x: x[1])
anss = 0
for i in l[-1::-1]:
	index = bisect.bisect_left(l2, i[0])
	if index < len(l2):
		anss += i[1]
		count += 1
		qq = lll.index(l2[index])
		lll[qq] = 0
		l2.pop(index)
		ans.append([i[2] + 1, qq + 1])
print(count, anss)
for i in ans:
	print(*i)


n = int(input())
ls = []
for i in range(n):
	(c, p) = map(int, input().split())
	ls.append([p, c, i + 1])
ls.sort(reverse=True)
k = int(input())
table = [[0] for i in range(1001)]
r = list(map(int, input().split()))
for i in range(k):
	table[r[i]].append(i + 1)
total = 0
ans = []
for i in range(n):
	for j in range(ls[i][1], 1001):
		if table[j][0] < len(table[j]) - 1:
			total += ls[i][0]
			ans.append([ls[i][2], table[j][table[j][0] + 1]])
			table[j][0] += 1
			break
print(len(ans), total)
for i in range(len(ans)):
	print(*ans[i])


import sys
n = int(sys.stdin.readline())
request = []
for i in range(1, n + 1):
	(people, cost) = map(int, sys.stdin.readline().split())
	request.append((i, people, cost))
k = int(sys.stdin.readline())
tables = []
for tmp in zip(range(1, k + 1), [int(s) for s in sys.stdin.readline().split()]):
	tables.append(tmp)
tables.sort(key=lambda item: item[1])
total = 0
ans = []
used = [False for i in range(n + 1)]
count = 0
for (i, t) in tables:
	max_price = 0
	request_id = -1
	for (j, c, p) in request:
		if p > max_price and c <= t and (not used[j]):
			max_price = p
			request_id = j
	if request_id > 0:
		count += 1
		used[request_id] = True
		ans.append((request_id, i))
		total += max_price
print(str(count) + ' ' + str(total))
for (request_id, i) in ans:
	print(str(request_id) + ' ' + str(i))


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
k = int(input())
b = list(map(int, input().split()))
r = max(b)
for i in range(n):
	if a[i][0] > r:
		a[i].append(1)
		a[i] = a[i][::-1]
		a[i].append(i + 1)
	else:
		a[i].append(0)
		a[i] = a[i][::-1]
		a[i].append(i + 1)
a.sort(reverse=True)
c = [[] for i in range(1001)]
for i in range(k):
	c[b[i]].append(i + 1)
mo = 0
ans = []
for i in range(n):
	if not a[i][0]:
		for j in range(a[i][2], r + 1):
			if len(c[j]) > 0:
				mo += a[i][1]
				ans.append([a[i][-1], c[j][0]])
				del c[j][0]
				break
print(len(ans), mo)
for i in ans:
	print(*i)


from bisect import bisect_left as bl
from collections import defaultdict
n = int(input())
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
d = defaultdict(list)
for i in range(n - 1, -1, -1):
	d[l[i][0], l[i][1]].append(i + 1)
k = int(input())
l1 = list(map(int, input().split()))
l2 = []
for i in range(k):
	l2.append([l1[i], i])
l2.sort()
l.sort()
ans1 = 0
ans2 = 0
ans = []
for i in range(k):
	if len(l) == 0:
		break
	a = bl(l, [l2[i][0], 1001])
	x = 0
	y = 0
	for j in range(a):
		if x <= l[j][1]:
			x = l[j][1]
			y = j
	if x:
		ans1 += 1
		ans2 += x
		ans.append([d[l[y][0], l[y][1]][-1], l2[i][1] + 1])
		d[l[y][0], l[y][1]].pop()
		l.pop(y)
print(ans1, ans2)
ans.sort()
for i in ans:
	print(*i)


class er:

	def __init__(self, ci, pi, id):
		self.c = ci
		self.p = pi
		self.id = id

	def __lt__(self, other):
		return self.p < other.p

	def __str__(self):
		return str(self.c) + ',' + str(self.p) + ',' + str(self.id)
n = int(input())
a = []
for i in range(n):
	(ci, pi) = map(int, input().split())
	a.append(er(ci, pi, i + 1))
k = int(input())
t = list(map(int, input().split()))
tb = [0] * k
a.sort(reverse=True)
(m, s) = (0, 0)
ans = []
for i in a:
	ind = -1
	for j in range(k):
		if i.c <= t[j] and tb[j] == 0:
			if ind == -1:
				ind = j
			elif t[j] < t[ind]:
				ind = j
	if ind != -1:
		m += 1
		s += i.p
		ans.append([i.id, ind + 1])
		tb[ind] = 1
print(m, s)
for i in ans:
	print(i[0], i[1])


from bisect import bisect_left

def read():
	return map(int, input().split())

def main():
	(n,) = read()
	requests = [tuple(read()) for _ in range(n)]
	(k,) = read()
	tables_size = list(read())
	tables_size = sorted([(idx, cap) for (idx, cap) in enumerate(tables_size)], key=lambda x: x[1])
	ts = [e[1] for e in tables_size]
	requests = sorted([(i, e) for (i, e) in enumerate(requests)], key=lambda x: x[1][1])
	num_acc_requests = 0
	total_money = 0
	ans = []
	while requests:
		(c, p) = requests.pop()
		if tables_size:
			idx = bisect_left(ts, p[0])
			if idx < len(tables_size):
				num_acc_requests += 1
				total_money += p[1]
				ans.append((c + 1, tables_size[idx][0] + 1))
				del tables_size[idx]
				del ts[idx]
	print(num_acc_requests, total_money)
	for e in ans:
		print(*e)
main()


n = int(input())
import heapq
heap = []
heapq.heapify(heap)
for i in range(n):
	s = input()
	s1 = s.split()
	temp = [-int(s1[1]), int(s1[0]), i]
	heapq.heappush(heap, temp)
k = int(input())
s = input()
s1 = s.split()
r = [int(i) for i in s1]
d = {}
for i in range(len(r)):
	if r[i] not in d:
		d[r[i]] = [i]
	else:
		d[r[i]].append(i)
r.sort()
final = []
profit = 0
cnt = 0
while heap:
	curr = heapq.heappop(heap)
	for i in range(len(r)):
		if curr[1] <= r[i]:
			profit = profit - curr[0]
			cnt = cnt + 1
			final.append([curr[2] + 1, d[r[i]][0] + 1])
			del d[r[i]][0]
			r[i] = 0
			break
s = str(cnt) + ' ' + str(profit)
print(s)
for i in final:
	print(*i)


n = int(input())
(request, ans) = ([], [])
for idx in range(n):
	request.append(list(map(int, input().split())) + [idx + 1])
k = int(input())
accept = 0
size = list(map(int, input().split()))
for idx in range(k):
	size[idx] = [size[idx], idx + 1]
size.sort()
request.sort(reverse=True, key=lambda x: x[1])
total_cost = 0
for idx in range(n):
	if size and size[-1][0] >= request[idx][0]:
		(l, r) = (0, k - 1 - accept)
		while l < r - 1:
			mid = (l + r) // 2
			if size[mid][0] < request[idx][0]:
				l = mid + 1
			else:
				r = mid
		if size[l][0] < request[idx][0]:
			l = r
		total_cost += request[idx][1]
		ans.append([request[idx][2], size[l][1]])
		del size[l]
		accept += 1
print(accept, total_cost)
for val in ans:
	print(val[0], val[1])


n = int(input(''))
group = []
table = []
for i in range(n):
	(size, money) = map(int, input('').split())
	group += [(money, size, i)]
k = int(input(''))
out = []
all_money = 0
table = list(map(int, input('').split()))
for (money, size, j) in reversed(sorted(group)):
	max = 1000
	uu = -1
	for (i, table1) in enumerate(table):
		if size <= table1 < max + 1:
			max = table1
			uu = i
	if uu > -1:
		table[uu] = 0
		out += [(j, uu)]
		all_money += money
print(len(out), all_money)
for (i, j) in out:
	print(i + 1, j + 1)


n = int(input())
g = []
for i in range(n):
	g.append(list(map(int, input().split()))[::-1])
g_copy = g[:]
a = int(input())
t = list(map(int, input().split()))
t_copy = t[:]
g.sort(reverse=True)
t.sort()
ans = []
s = 0
k = 0
for group in g:
	for table in range(len(t)):
		if group[1] <= t[table]:
			k += 1
			s += group[0]
			ans.append([group, t[table]])
			t[table] = 0
			break
print(k, s)
for answer in ans:
	gr = answer[0]
	ta = answer[1]
	ig = g_copy.index(gr)
	it = t_copy.index(ta)
	print(ig + 1, end=' ')
	print(it + 1, end='')
	g_copy[ig] = -1
	t_copy[it] = -1
	print()


def low_bound(mas, x):
	l = 0
	r = len(mas) - 1
	while l < r:
		m = (l + r) // 2
		if mas[m][0] >= x:
			r = m
		else:
			l = m + 1
	return l
n = int(input().strip())
gr = []
for i in range(n):
	gr.append(list(map(int, input().split()))[::-1] + [i + 1])
k = int(input().strip())
tab = [[v, i + 1] for (i, v) in enumerate(list(map(int, input().split())))]
gr.sort(reverse=True)
ans = []
s = 0
tab.sort()
for (p, cnt, ind) in gr:
	if len(tab) > 0 and tab[-1][0] >= cnt:
		s += p
		i = low_bound(tab, cnt)
		ans.append((ind, tab[i][1]))
		tab.remove(tab[i])
print(len(ans), s)
for i in ans:
	print(*i)
tab.sort()


def findSeat(seats, cap):
	for i in range(len(seats)):
		if cap <= seats[i][0]:
			return i
	return -1
n = int(input())
visitors = []
for i in range(n):
	(c, p) = map(int, input().split(' '))
	visitors.append([c, p, i])
visitors.sort(key=lambda x: x[1], reverse=True)
k = int(input())
seats = list(map(int, input().split(' ')))
seats_new = []
for i in range(len(seats)):
	seats_new.append([seats[i], i])
seats = seats_new
seats.sort(key=lambda x: x[0])
ans = 0
allotment = []
for i in range(len(visitors)):
	(cap, price, entry) = visitors[i]
	idx = findSeat(seats, cap)
	if idx == -1:
		continue
	else:
		seats[idx][0] = -1
		ans += price
		allotment.append([entry + 1, seats[idx][1] + 1])
print(len(allotment), ans)
for allots in allotment:
	print(allots[0], allots[1])


def smaller(a, val, vis):
	ind = None
	for i in range(len(a)):
		if a[i] >= val and vis[i] == 0:
			if ind != None:
				if a[i] < a[ind]:
					ind = i
			else:
				ind = i
	return ind

def f(p, a):
	for i in range(len(p)):
		p[i].append(i)
	p = sorted(p, key=lambda s: s[1], reverse=True)
	ans = []
	s = 0
	vis = [0] * len(a)
	for i in p:
		ind = smaller(a, i[0], vis)
		if ind != None:
			ans.append([i[2] + 1, ind + 1])
			vis[ind] = 1
			s += i[1]
	print(len(ans), s)
	for i in ans:
		print(*i)
	return ''
p = []
for i in range(int(input())):
	(a, b) = map(int, input().strip().split())
	p.append([a, b])
k = input()
ar = list(map(int, input().strip().split()))
print(f(p, ar))


import sys
import math
import collections
import bisect

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
for t in range(1):
	n = int(input())
	cost_array = []
	for i in range(n):
		(c, p) = get_ints()
		cost_array.append([p, c, i])
	dup_cost_array = cost_array.copy()
	cost_array.sort()
	k = int(input())
	table = get_list()
	selected = [10 ** 5] * k
	for i in range(n - 1, -1, -1):
		cost = cost_array[i][0]
		people = cost_array[i][1]
		index = cost_array[i][2]
		pos = 10000
		val = 10 ** 10
		for j in range(k):
			if table[j] >= people and selected[j] == 10 ** 5:
				if table[j] < val:
					val = table[j]
					pos = j
		if pos != 10000:
			selected[pos] = index
	ans = []
	cost = 0
	number_of_people = 0
	for i in range(k):
		if selected[i] != 10 ** 5:
			req_no = selected[i] + 1
			table_no = i + 1
			ans.append([req_no, table_no])
			number_of_people += 1
			cost += dup_cost_array[req_no - 1][0]
	print(number_of_people, cost)
	for i in ans:
		print(*i)


def main():
	F = lambda : map(int, input().split())
	n = int(input())
	groups = [list(F())[::-1] + [i] for i in range(n)]
	k = int(input())
	tables = list(F())
	tables = [[tables[i], i] for i in range(k)]
	tables = sorted(tables)
	groups = sorted(groups)
	count = 0
	SUM = 0
	res = []
	for i in range(n - 1, -1, -1):
		for j in range(len(tables)):
			if tables:
				if groups[i][1] <= tables[j][0]:
					res.append([groups[i][2], tables[j][1]])
					count += 1
					SUM += groups[i][0]
					tables.pop(j)
					break
			else:
				return [count, SUM, res]
	return [count, SUM, res]
answer = main()
print(answer[0], answer[1])
for x in answer[2]:
	print(x[0] + 1, x[1] + 1)


from sys import stdin, stdout
import bisect
n = int(input())
size = []
money = []
for _ in range(n):
	(ci, pi) = map(int, stdin.readline().split(' '))
	size.append(ci)
	money.append(pi)
groupno = [i + 1 for i in range(n)]
k = int(input())
table = list(map(int, stdin.readline().split(' ')))
tid = [i + 1 for i in range(k + 1)]
td = {}
t1 = sorted(zip(table, tid))
table = [x for (x, y) in t1]
tid = [y for (x, y) in t1]
for i in range(k):
	td[i + 1] = -1
t1 = sorted(zip(money, size, groupno))
size = [y for (x, y, z) in t1]
groupno = [z for (x, y, z) in t1]
money = [x for (x, y, z) in t1]
money.reverse()
groupno.reverse()
size.reverse()
ans = 0
ans1 = 0
for i in range(len(money)):
	t1 = bisect.bisect_left(table, size[i])
	if t1 != len(table):
		td[tid[t1]] = groupno[i]
		ans += money[i]
		ans1 += 1
		tid.pop(t1)
		table.pop(t1)
print(ans1, ans)
for i in td:
	if td[i] != -1:
		stdout.write(str(td[i]) + ' ' + str(i) + '\n')


n = int(input())
pos = []
for i in range(n):
	(vvod1, vvod2) = map(int, input().split())
	pos.append([vvod2, vvod1])
dop1 = pos.copy()
pos.sort()
pos.reverse()
k = int(input())
sto = list(map(int, input().split()))
dop2 = sto.copy()
sto.sort()
kol = 0
suma = 0
vivod = []
for y in range(n):
	for x in range(k):
		if pos[y] != '' and sto[x] != '' and (pos[y][1] <= sto[x]):
			vivod.append([pos[y], sto[x]])
			suma += pos[y][0]
			kol += 1
			pos[y] = ''
			sto[x] = ''
			break
print(kol, suma)
for i in range(kol):
	x = dop1.index(vivod[i][0])
	y = dop2.index(vivod[i][1])
	print(x + 1, y + 1)
	dop1[x] = ''
	dop2[y] = ''


n = int(input())
s = []
for i in range(n):
	(c, p) = map(int, input().split())
	s.append((p, c, i))
z = s[:]
k = int(input())
m = list(map(int, input().split()))
s.sort()
s.reverse()
answ = 0
summ = 0
sisok = []
f = 'lopata'
for i in range(n):
	price = s[i][0]
	col = s[i][1]
	index = s[i][2]
	zn = 100000001
	uk = -1
	for j in range(k):
		if col <= m[j] < zn:
			uk = j
			zn = m[j]
	if uk != -1:
		m[uk] = 0
		sisok.append((index + 1, uk + 1))
		summ += price
print(len(sisok), summ)
for x in sisok:
	print(*x)


n = int(input())
book = [None] * n
for i in range(n):
	t = [int(i) for i in input().split(' ')]
	book[i] = (i, t[0], t[1])
k = int(input())
cap = [(i, int(c)) for (i, c) in enumerate(input().split(' '))]
cap.sort(key=lambda x: x[1])
book.sort(key=lambda x: x[1])
m = 0
s = 0
r = []
cand = []
j = 0
for i in range(k):
	while j < len(book) and cap[i][1] >= book[j][1]:
		cand.append((book[j][0], book[j][2]))
		j += 1
	if len(cand) == 0:
		continue
	cand.sort(key=lambda x: x[1])
	m += 1
	s += cand[-1][1]
	r.append((cand.pop()[0] + 1, cap[i][0] + 1))
print(m, s)
for i in range(m):
	print(r[i][0], r[i][1])


import sys

class Visitor:

	def __init__(self, pi, ci, i):
		self.ci = ci
		self.pi = pi
		self.i = i
		self.place = None

	def __repr__(self):
		return '{} {} {}'.format(self.ci, self.pi, self.i)

class Place:

	def __init__(self, i, max_):
		self.i = i
		self.max_ = int(max_)

	def __repr__(self):
		return '{} {}'.format(self.max_, self.i)
lines = sys.stdin.readlines()
n = int(lines[0])
visitors = []
for i in range(1, n + 1):
	(ci, pi) = lines[i].split()
	visitors.append(Visitor(int(pi), int(ci), i))
places = []
for (i, place) in enumerate(lines[n + 2].split()):
	places.append(Place(i + 1, place))
visitors = sorted(visitors, key=lambda x: x.pi)[::-1]
places = sorted(places, key=lambda x: x.max_)
visited = [None for _ in places]
total = 0
for visitor in visitors:
	for (i, place) in enumerate(places):
		if visitor.ci <= place.max_ and visited[i] is None:
			visited[i] = visitor
			visitor.place = place
			total += visitor.pi
			break
new_visitors = list(filter(lambda x: x.place is not None, sorted(visitors, key=lambda x: x.i)))
print('{} {}'.format(len(new_visitors), total))
for visitor in new_visitors:
	print('{} {}'.format(visitor.i, visitor.place.i))


n = int(input())
people = []
for i in range(n):
	inp = input().split()
	(p, c) = (int(inp[0]), int(inp[1]))
	people.append([c, p, i + 1])
people.sort()
k = int(input())
z = input().split()
v = [[int(z[i]), i + 1] for i in range(k)]
v.sort()
tot = 0
s = 0
ans = []
for i in range(n - 1, -1, -1):
	for j in range(len(v)):
		if v[j][0] >= people[i][1]:
			tot += people[i][0]
			ans.append([people[i][2], v[j][1]])
			s += 1
			v.remove(v[j])
			break
print(s, tot)
for i in range(s):
	print(ans[i][0], ans[i][1])


from sys import stdin, stdout
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	n = nmbr()
	l = [lst() for _ in range(n)]
	m = nmbr()
	sm = 0
	a = sorted(zip(lst(), range(m)))
	vis = {}
	for i in range(m):
		mx = 0
		p = -1
		for j in range(n):
			if j not in vis and l[j][0] <= a[i][0] and (mx <= l[j][1]):
				mx = l[j][1]
				p = j
		if p != -1:
			vis[p] = a[i][1]
			sm += mx
	print(len(vis), sm)
	for (k, v) in vis.items():
		print(k + 1, v + 1)


n = int(input())
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
	l[i] += [i + 1]
k = int(input())
s = list(map(int, input().split()))
for i in range(k):
	s[i] = [i + 1, s[i]]

def fun(itm):
	return itm[1]
l.sort(reverse=True, key=fun)
s.sort(key=fun)
ans = 0
ansl = []
for i in l:
	for j in s:
		if i[0] <= j[1]:
			ans += i[1]
			s.remove(j)
			ansl.append([i[2], j[0]])
			break
print(len(ansl), ans)
for i in ansl:
	print(i[0], i[1])


n = int(input())
vs = list()
for i in range(n):
	(a, b) = map(int, input().strip().split())
	vs.append([b, a, i + 1])
vs.sort(reverse=True)
k = int(input())
tb = list()
j = 1
for i in map(int, input().strip().split()):
	tb.append([i, j])
	j += 1
tb.sort()
i = 0
ans = 0
ans_ar = list()
while len(tb) > 0 and i < len(vs):
	l = 0
	r = len(tb) - 1
	mid = int(r / 2)
	while l < r:
		if vs[i][1] > tb[mid][0]:
			l = mid + 1
		else:
			r = mid
		mid = int((l + r) / 2)
	if vs[i][1] <= tb[r][0]:
		ans += vs[i][0]
		ans_ar.append([vs[i][2], tb[r][1]])
		tb.pop(r)
	i += 1
print('{} {}'.format(len(ans_ar), ans))
for i in range(len(ans_ar)):
	print('{} {}'.format(ans_ar[i][0], ans_ar[i][1]))


import heapq

def binarySearch(ele, lst, l=None, h=None):
	if l == None:
		l = 0
	if h == None:
		h = len(lst) - 1
	while h >= l:
		m = l + (h - l) // 2
		if lst[m][0] > ele:
			h = m - 1
		if lst[m][0] <= ele:
			l = m + 1
	return h

def main():
	req = int(input())
	items = []
	for index in range(req):
		(c, p) = map(int, input().split(' '))
		items.append((c, -1 * p, index + 1))
	_ = input()
	t = list(map(int, input().split(' ')))
	tables = []
	for (i, ele) in enumerate(t):
		tables.append((ele, i + 1))
	tables.sort()
	items.sort()
	heap = []
	total = 0
	accepted = 0
	ans = []
	startingIndex = 0
	for (ele, tNum) in tables:
		index = binarySearch(ele, items)
		for i in range(startingIndex, index + 1):
			heapq.heappush(heap, (items[i][1], items[i][2]))
		startingIndex = index + 1
		if heap:
			(value, request) = heapq.heappop(heap)
			accepted += 1
			total += value
			ans.append((request, tNum))
	print(accepted, abs(total))
	for (req, table) in ans:
		print(req, table)
main()


n = int(input())
d = {}
for x in range(n):
	(grp, m) = map(int, input().strip().split())
	if m not in d:
		d[m] = [[grp, x + 1]]
	else:
		d[m].append([grp, x + 1])
k = int(input())
arr = list(map(int, input().strip().split()))
sums = 0
count = 0
last = -1
lis = []
for e in sorted(d.keys(), reverse=True):
	for i in d[e]:
		diff = 100000
		f = 0
		for y in range(len(arr)):
			if arr[y] - i[0] >= 0 and i[0] <= arr[y]:
				if diff > arr[y] - i[0]:
					diff = arr[y] - i[0]
					last = y
					f = 1
		if f == 1:
			lis.append([i[1], last + 1])
			arr[last] = -1
			count += 1
			sums += e
print(count, sums)
for l in lis:
	print(*l)


n = int(input())
c = []
for i in range(n):
	c.append(list(map(int, input().split())))
	c[i].append(i + 1)
r = int(input())
k = list(map(int, input().split()))

def sortfn(inp):
	return inp[1]
c.sort(key=sortfn, reverse=True)
for i in range(len(k)):
	val = k[i]
	k[i] = [i + 1, val]
k.sort(key=sortfn)

def gettable(size):
	for i in range(len(k)):
		if k[i][1] >= size:
			k[i][1] = -1
			table = k[i][0]
			return table
	return -1
groups = []
val = 0
for group in c:
	table = gettable(group[0])
	if table > 0:
		groups.append([str(group[2]), str(table)])
		val += group[1]
print(str(len(groups)) + ' ' + str(val))
for g in groups:
	print(' '.join(g))


import os
from sys import stdin, stdout
from heapq import heappush, heappop

def solve(tc):
	n = int(stdin.readline().strip())
	people = []
	for i in range(n):
		(ci, pi) = map(int, stdin.readline().split())
		people.append([ci, pi])
	pidx = list(range(n))
	pidx = sorted(pidx, key=lambda x: people[x])
	k = int(stdin.readline().strip())
	tables = list(map(int, stdin.readline().split()))
	tidx = list(range(k))
	tidx = sorted(tidx, key=lambda x: tables[x])
	ans = []
	tot = 0
	p = 0
	heap = []
	for i in range(k):
		while p < n and people[pidx[p]][0] <= tables[tidx[i]]:
			heappush(heap, [-people[pidx[p]][1], pidx[p]])
			p += 1
		if len(heap) > 0:
			top = heappop(heap)
			tot -= top[0]
			ans.append([top[1] + 1, tidx[i] + 1])
	print(len(ans), tot)
	for i in range(len(ans)):
		print(' '.join(map(lambda x: str(x), ans[i])))
tcs = 1
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1