CF166D Shoe Store

你的商店仓库中有 $n$ 双鞋。每一双鞋由两个整数描述：它的价格 $c_i$ 和它的鞋码 $s_i$。已知今天所有 $s_i$ 互不相同，也就是说每一个鞋码最多只有一双鞋。 商店有 $m$ 个顾客同时到来。第 $i$ 个顾客有 $d_i$ 的钱，并且他的脚的尺码为 $l_i$。顾客 $i$ 可以购买第 $j$ 双鞋，如果 $c_j \leq d_i$，并且 $l_i = s_j$ 或 $l_i = s_j - 1$；也就是说，顾客的钱要足够支付该双鞋，并且他的脚码与鞋的鞋码要相等，或正好小一号。 你的任务是（每个顾客最多买一双，每双鞋最多卖给一个顾客）安排售鞋顺序，使得卖出鞋的总金额 $c_j$ 之和最大（即最大化利润）。 保证所有 $s_i$ 不同，每个顾客最多买一双鞋，每双鞋最多只卖给一个顾客。

第一行输入一个整数 $n$（$1 \leq n \leq 10^{5}$），表示仓库里的鞋的数量。接下来 $n$ 行，每行描述一双鞋，含两个整数 $c_i$ 和 $s_i$（$1 \leq c_i,s_i \leq 10^{9}$），用空格分隔。已知所有 $s_i$ 互不相同。 接下来一行输入一个整数 $m$（$1 \leq m \leq 10^{5}$），表示到店的顾客数量。接下来 $m$ 行，每行描述一个顾客，含两个整数 $d_i$ 和 $l_i$（$1 \leq d_i,l_i \leq 10^{9}$），用空格分隔。

第一行输出一个整数，表示所能获得的最大利润。 第二行输出一个整数 $k$，表示你将售出的鞋的数量。 接下来的 $k$ 行，每行输出两个用空格分隔的整数，分别为顾客编号和鞋子编号，表示该顾客购买了哪一双鞋。 你可以按任意顺序输出每组“顾客编号 鞋子编号”，顾客和鞋子的编号均按照输入的顺序从 1 开始。如果有多组最优解，输出任意一组都可以。

由 ChatGPT 5 翻译