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: interview

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())
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])


n=int(input())
P=[]
for i in range(n):
    x,y=list(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


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)

def __starting_point():
    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([x for x in sorted(visitors, key=lambda x: x.i) if x.place is not None])
    print("{} {}".format(len(new_visitors), total))
    for visitor in new_visitors:
        print("{} {}".format(visitor.i, visitor.place.i))

    # print(visitors)
    # print(places)
    # print(visited)

__starting_point()

n=int(input(''))
group=[]
table=[]
for i in range(n):
    size,money=list(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())
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)

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))

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 sys

# request number
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))

#request.sort(key=lambda item: (-item[2], item[1]))
#print(request)

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])
#print(tables)

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

#sorted(ans)
print( str(count) + " " + str(total) )
for request_id, i in ans:
  print( str(request_id) + " " + str(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()))
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())
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()) # request number
x=[] # requests array
for i in range(n): # input requests array
    c,p=map(int, input().split())
    x+=[(p,c,i)] # please note: p is value
k=int(input()) # table number
r=list(map(int, input().split())) #tables array
s=0 # sum
q=[] # results array
for (v,c,a) in reversed(sorted(x)): # v=value c=cost
    p=-1
    u=100000
    for (j,z) in enumerate(r): # j=index, z=value
        if c<=z<u: # request size <= table index < cur index
            p=j
            u=z
    if p>-1: 
        r[p]=0   # make table size=0 indicates it has been used.
        q+=[(a,p)]
        s+=v
print(len(q),s)
for (i, j) in q:
    print(i+1, j+1)

n=int(input())
x=[]
for i in range(n):
    c,p=list(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=10000
    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())
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=10000
    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())
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())
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=1001
    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)

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()


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))


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)


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)

# -*- coding: utf-8 -*-
"""
Created on Sat Oct 15 00:37:04 2016

@author: Arpan
"""

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])
            



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))


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 = []
reserved = [0 for _ in range(n)]
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] and not reserved[i[2]-1] :
            maxx = i
        elif i[0] > maxx[0] and i[1] <= j[0] and not reserved[i[2]-1] :
            maxx = i
    if maxx[2] != 0 :
        accepted.append((maxx[2],j[1]))
        reserved[maxx[2]-1] = 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])


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 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))