← 返回题目列表

Codeforces · 416/C

C. 预订系统

中文机器翻译题面 查看原题

创新技术正在全球范围内取得胜利。它们融入了人类活动的各个领域!

一家名为“Dijkstra's Place”的餐厅已经开始考虑优化预订系统。

目前已收到 n 个预订请求。每个请求都由两个数字来表征:ci 和 pi——通过该请求前来的访客群体的规模以及他们将在餐厅相应消费的总金额。

我们知道,对于每个请求,所有 ci 人都想坐在同一张桌子上,并且会在餐厅里度过整个晚上,从 18:00 开始营业到结束营业。

不幸的是,餐厅里只有 k 张桌子。对于每张桌子,我们都知道 ri——可以坐在该桌子上的最大人数。一张桌子只能容纳来自同一组的人。如果您找不到足够大的桌子容纳整个团体,那么所有访客都会离开,自然无需支付任何费用。

您的任务是:根据表格和请求,决定接受哪些请求以及拒绝哪些请求,以便快乐而充实的访客支付的费用最大化。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 1000) — 访问者的请求数。然后是n行。每行包含两个整数:ci, pi (1 ≤ ci, pi ≤ 1000)——相应地,第 i 个请求将到来的访客群体的规模以及他们访问餐厅时将支付的总金额。

下一行包含整数 k (1 ≤ k ≤ 1000) — 餐厅的桌子数量。最后一行包含 k 个空格分隔的整数:r1, r2, ..., rk (1 ≤ ri ≤ 1000) — 每张桌子可以坐的最大人数。

输出

在第一行打印两个整数:m、s——相应地,接受的请求数以及您从这些请求中获得的总金额。

然后打印 m 行 - 每行必须包含两个空格分隔的整数:接受的请求的编号以及通过此请求而来的座位的桌子编号。请求和表按照输入中给出的顺序从 1 开始连续编号。

如果有多个最佳答案,则打印其中任何一个。

示例

输入 #1

3
10 50
2 100
5 30
3
4 6 9

输出 #1

2 130
2 1
3 2