你店里的仓库有n双鞋。每对都有两个整数:价格 ci 和大小 si。我们知道,在这一天,所有数字 si 都是不同的,也就是说,每种尺寸最多只有一对。
该店有 m 位顾客同时来店。顾客号i有钱di,脚的尺寸等于li。如果 cj ≤ di,并且 li = sj 或 li = sj - 1,则编号 i 的顾客可以购买编号 j 的配对;也就是说,他必须有足够的钱来支付鞋子的费用。还需要他的脚的尺寸等于或小于他选择的鞋子的尺寸1。
你的任务是向一些顾客出售双鞋(每人一双),以使所售双鞋的总和 cj 最大化,即利润。保证每位顾客购买不超过一双,每双购买的顾客不超过一位。
输入
第一个输入行包含唯一的整数 n (1 ≤ n ≤ 105) — 仓库中鞋对的数量。然后n行包含对鞋子的描述作为两个整数ci和si(1≤ci,si≤109),数字之间用空格分隔。保证所有数字 si 都不同。
下一行包含一个整数 m (1 ≤ m ≤ 105) — 商店中的顾客数量。接下来的 m 行包含客户的描述,作为两个整数 di 和 li (1 ≤ di, li ≤ 109),数字之间用空格分隔。
输出
第一行打印唯一的整数——卖鞋能获得的最大利润。在第二行中打印一个整数 k — 您将出售的鞋对的数量。在接下来的 k 行中,打印已售出的鞋子的描述 - 两个空格分隔的整数,其中第一个数字是客户的编号,第二个数字是客户将购买的鞋子的编号。
您可以按任意顺序打印数字对“客户编号和鞋子编号”,客户和鞋子按照输入中给出的顺序从 1 开始编号。如果有多个最佳答案,您可以打印其中任何一个。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位数字。最好使用 cin、cout 流或 %I64d 指定符来代替。
示例
输入 #1
3 10 1 30 2 20 3 2 20 1 20 2
输出 #1
30 2 2 3 1 1
输入 #2
3 10 4 20 5 30 6 2 70 4 50 5
输出 #2
50 2 2 3 1 2