CF416C Booking System

创新技术正在全球范围内蓬勃发展，并逐渐融入人类活动的各个领域！ 一家名为 “Dijkstra's Place” 的餐厅开始考虑优化其订位系统。 目前已经收到 $n$ 个订位请求。每个请求由两个数字 $c_i$ 和 $p_i$ 表示—— $c_i$ 表示本次请求的来客人数，$p_i$ 表示这批客人在餐厅消费的总金额。 我们知道，对于每一个请求，所有 $c_i$ 个人希望坐在同一张桌子上，并且他们会在餐厅度过整个晚上——从开门的 18:00 一直到打烊。 不幸的是，餐厅只有 $k$ 张桌子。对于每一张桌子，我们都知道 $r_i$——这张桌子可容纳的最多人数。一张桌子只能接待同一组的客人。如果没有足够大的桌子容纳某个订位请求的所有客人，这组客人就会离开，且不会产生任何消费。 你的任务是：根据餐厅的桌子情况和订位请求，决定接受哪些请求、拒绝哪些请求，以使满意且吃饱的客人所支付的总金额最大。

输入的第一行为整数 $n$（$1\le n\le 1000$）——来自顾客的订位请求数。接下来的 $n$ 行，每行包含两个整数 $c_i,p_i$（$1\le c_i,p_i\le 1000$）——第 $i$ 个订位请求的客人数和他们愿意支付的总金额。 之后一行包含一个整数 $k$（$1\le k\le 1000$）——餐厅里的桌子数。最后一行包含 $k$ 个用空格分隔的整数 $r_1, r_2, ..., r_k$（$1\le r_i\le 1000$）——每张桌子的最大容纳人数。

在第一行输出两个整数 $m,s$——被接受的请求数和这些请求带来的总金额。 接下来输出 $m$ 行，每行两个用空格分隔的整数，表示被接受的请求编号和为该请求安排的桌子编号。请求和桌子编号均从 $1$ 开始，编号顺序与输入一致。 如果存在多组最大总金额的方案，请输出任意一组。

由 ChatGPT 5 翻译