Shoe Store

题意翻译

## 题目描述 你开了一家鞋店。今天是个特别的日子（？？）——今天你的仓库里有 $n$ 双鞋，每双鞋有两个参数：$c_i$表示价格、$s_i$表示尺码——为什么今天特别呢？因为你发现仓库里没有两双相同尺码的鞋，也就是说对于任意 $i,j(i≠j)$ ，满足 $s_i≠s_j$ 。 这时，同时来了 $m$ 个顾客。第 $i$ 个顾客带了 $d_i$ 块钱，他可以穿的鞋的尺码是 $l_i$ **或** $(l_i-1) $。一个顾客可以买一双鞋当且仅当鞋的价格小于等于他携带的钱 且 鞋的尺码对他来说合适。 你希望卖出的鞋的总价格尽可能高，求你能卖出鞋的总价格最大为多少。 ## 输入 第一行为整数 $n$，表示鞋有多少双；接下来 $n$ 行，每行包括两个整数 $c_i,s_i$ ，表示第 $i$ 双鞋的价格和尺码。 下一行为整数 $m$，表示顾客的数量；接下来 $m$ 行，每行包括两个整数 $d_i,l_i$，表示第 $i$ 个顾客携带的钱的数量、适合他的尺码（适合他的尺码为 $l_i,l_i-1$）。 ## 输出 第一行为一个整数表示你卖出鞋的最大总价格； 第二行为一个整数 $k$，表示你卖出了多少双鞋； 接下来的$k$行，包括两个数，即“顾客编号$x_i$ 鞋编号$y_i$”，表示把鞋 $y_i$ 卖给 $x_i$。

题目描述

The warehouse in your shop has $ n $ shoe pairs. Each pair is characterized by two integers: its price $ c_{i} $ and its size $ s_{i} $ . We know that on this very day all numbers $ s_{i} $ are different, that is, there is no more than one pair of each size. The shop has $ m $ customers who came at the same time. The customer number $ i $ has $ d_{i} $ money and the size of his feet equals $ l_{i} $ . The customer number $ i $ can buy the pair number $ j $ , if $ c_{j}<=d_{i} $ , and also if $ l_{i}=s_{j} $ or $ l_{i}=s_{j}-1 $ ; that is, it is necessary that he has enough money to pay for the shoes. It is also necessary that the size of his feet equals to or is less by $ 1 $ than the size of the shoes he chooses. Your task is to sell some customers pairs of shoes (a pair per person) so as to maximize the sum of the sold pairs $ c_{j} $ that is, the profit. It is guaranteed that each customer buys no more than one pair and each pair will be bought by no more than one customer.

输入输出格式

输入格式

The first input line contains the only integer $ n $ ( $ 1<=n<=10^{5} $ ) — the number of shoe pairs in the warehouse. Then $ n $ lines contain the descriptions of pairs of shoes as two integers $ c_{i} $ and $ s_{i} $ ( $ 1<=c_{i},s_{i}<=10^{9} $ ), the numbers are separated by a space. It is guaranteed that all numbers $ s_{i} $ are different. The next line contains an integer $ m $ ( $ 1<=m<=10^{5} $ ) — the number of customers in the shop. Next $ m $ lines contain the customers' descriptions as two integers $ d_{i} $ and $ l_{i} $ ( $ 1<=d_{i},l_{i}<=10^{9} $ ), the numbers are separated by a space.

输出格式

In the first line print the only integer — the maximum profit you can get from selling shoes. In the second line print an integer $ k $ — the number of shoe pairs you will sell. In the following $ k $ lines print the descriptions of the sold pairs — two space-separated integers where the first number is the customer's number and the second number is the number of the shoes the customer will buy. You can print pairs of numbers "the customer's number and the shoes' number" in any order, the customers and the pairs of shoes are numbered starting from $ 1 $ in the order in which they are given in the input. If there are several optimal answers, you are allowed to print any of them. Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin, cout streams or the %I64d specificator instead.

输入输出样例

输入样例 #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