CF416C.Booking System

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.

创新技术正在全球范围内高歌猛进，已融入人类活动的各个领域！

一家名为“Dijkstra's Place”的餐厅开始思考如何优化其预订系统。

截至目前，餐厅共收到 $n$ 个预订请求。每个请求由两个数表征：$c_i$ 和 $p_i$ —— 分别表示通过该请求前来就餐的顾客人数，以及他们将在餐厅消费的总金额。

我们知道，对于每个请求，全部 $c_i$ 位顾客都希望坐在同一张餐桌上，并且将从餐厅开门时刻（18:00）起一直待到打烊。

不幸的是，餐厅内仅有 $k$ 张餐桌。对每张餐桌 $i$，我们已知其最大容纳人数 $r_i$。每张餐桌仅能容纳来自同一组顾客；若无法为某个整组顾客找到一张容量足够大的餐桌，则该组所有顾客都将离开，自然也不会产生任何消费。

你的任务是：在给定餐桌信息与预订请求的前提下，决定接受哪些请求、拒绝哪些请求，使得最终成功入座并满意就餐的顾客所支付的总金额最大化。

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.

输入的第一行包含一个整数 $n$（$1 ≤ n ≤ 1000$）—— 表示访客的请求数量。接下来是 $n$ 行，每行包含两个整数：$c_i$ 和 $p_i$（$1 ≤ c_i, p_i ≤ 1000$）—— 分别表示第 $i$ 个请求中访客组的人数，以及该组访客到餐厅消费时支付的总金额。

下一行包含一个整数 $k$（$1 ≤ k ≤ 1000$）—— 表示餐厅中餐桌的数量。最后一行包含 $k$ 个用空格分隔的整数：$r_1,\,r_2,\,...,\,r_k$（$1 ≤ r_i ≤ 1000$）—— 表示每张餐桌最多可容纳的人数。

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.

第一行输出两个整数：$m$ 和 $s$ —— 分别表示被接受的请求数量以及从这些请求中获得的总金额。

接下来输出 $m$ 行，每行必须包含两个用空格分隔的整数：被接受的请求的编号，以及为通过该请求前来就餐的顾客所分配的餐桌编号。请求和餐桌均按输入中出现的顺序依次编号，编号从 1 开始。

若存在多个最优解，输出任意一个即可。