文理学院程序设计在线练习


模拟交易系统

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 81   Accepted Submission(s): 43
Problem Description

2007年中国股市,几家欢喜几家忧,几家割肉几家留。如果说2007年还让人还有所期待,2008年股市就让大多数散户绝望到了底谷。要炒好股有时做些技术分析是有必要的,通常成交量的大小在技术分析中就起着重要的作用。所以现在就来模拟下简化了的交易系统,并计算其成交量。交易所里的电脑交易系统决定一笔交易能否成交就是判断买入价是否大于或等于卖出价。当有多个报价的情况下,会根据价格优先,即最高的买入价会和最低卖出价优先成交。

举例来说,现在有四个买家,买入需求(“报价 数量”形式)分别是13元 5手(注:表示以13元的价格买入5手,手是数量单位),9元 10手,11元 10手,12元 5手;四个卖家,卖出需求(“报价 数量”形式)分别是11元 5手,9元 5手,10元 10手,12元 5手。首先,交易系统先会把买家的报价按价格从高到低排列,把卖家的报价按价格从低到高排列,然后进行撮合。

以下是按报价排序后的买卖双方:



撮合的过程是:买一的5手和卖一的5手成交;买二的5手和卖二的5手成交,卖二还剩5手未成交;买三的其中5手和卖二的5手成交;买三剩余的5手和卖三的5手成交;因为买四的价格小于卖四的价格,因此不能成交。至此,交易过程结束,总的成交量是20手。

Input

输入数据首先包含一个整数T (1<=T<=20),表示测试实例的个数,然后是T组测试数据。对于每组测试数据,首先是整数B (0<=B<1000),代表买入委托总数,接着是B行不同价格的买入委托,每行由2个整数P和N (0<P,N<1000)组成,分别代表买入价格和数量。然后是整数S (0<=S<1000),代表卖出委托总数,接着是S行不同价格的卖出委托,每行由2个整数由P和N (0<P,N<1000)组成,分别代表卖出价格和数量。

Output

对于每组测试数据,在一行上输出一个整数,表示成交量。

Sample Input
1
3
100 10
80 40
90 30
4
90 30
70 40
80 10
100 20
Sample Output
50
Author

Chen JingZuan

Source

zscas第三届程序设计竞赛