Problem 1081 --Botnet

1081: Botnet

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 17  Solved: 6
[Submit][Status][Web Board][Creator:]

Description

gungun正在学习关于 DDoS(分布式拒绝服务攻击)的知识,她了解到攻击者往往通过掌握 Botnet(僵尸网络)来进行攻击,当大量恶意用户的请求同一时间涌入同一台服务器时,服务器就很有可能无法再服务其他正常的用户。

zyyyyy看到gungun正在学习 DDoS,就把自己曾经悲催掉的服务器的访问日志给了她,zyyyyy很想知道服务器当时到底承受了多大的打击,也就是进行攻击的 Botnet 规模到底有多大!当某个IP地址在任意连续的AA秒内访问了服务器超过BB次,我们就认为该地址属于 Botnet。

gungun知道这其实就是求满足上述条件的IP地址的个数,但是gungun的作业实在太多了,她只能请你帮帮忙,赶紧求出来打发zyyyyy。

Input

第一行一个整数n,表示记录条数。

后面n行,每行以两个整数tsi mi开始,分别表示秒时间戳、子记录条数,接着是mi个有序对,每个有序对aij kij,分别表示IPv6地址、在该条记录里该地址的访问次数。数据保证tsi从小到大,但可以重复出现。

最后一行两个整数A B,见题目描述。

IPv6地址有很多种表示方法,其长度为128bit,在本题中我们简化如下:

  1. 首选形式为X:X:X:X:X:X:X:X,共八个X,其中每个X代表16bit,以十六进制显示,如 ABCD:EF01:2345:6789:ABCD:EF01:2345:6789

  2. 1的基础上,每个分段中的前导0可以省略(每个X中前面连续的0可以省略不写,若整个X都为0,则用一个0表示整个X),如 2001:0DB8:0000:0023:0008:0800:200C:417A 与 2001:DB8:0:23:8:800:200C:417A 等价。

  3. 2的基础上,如果有连续的超过一个分段为0,则可以使用特殊符号"::"进行代替,如 1080:0:0:0:8:800:200C:417A 与 1080::8:800:200C:417A 等价;FF01:0:0:0:0:0:0:0 与 FF01:: 等价。特殊符号"::"仅能出现一次,否则会造成地址的多义性,但出现的位置可以选择,如 FE80::9A:FE:0:0:4CA2 与 FE80:0:0:9A:FE::4CA2 等价;而 FE80::9A:FE::4CA2 不是合法的地址。

本题保证给出的日志中所有地址均为合法地址,但可能使用不同的表示方法,同一个IPv6地址的不同表示方法仍然只能算作一个地址。

1n103

1tsi2×109

1mi103

1kij107

1A,B2×109

aij仅包含数字0-9、大写字母A-F以及冒号":"

此外,1i=1nmi106,本质不同的地址个数不超过105

Output

一行一个整数,表示僵尸网络的规模。

Sample Input

10
1561910404 1 ABCD:EF01:2345:6789:ABCD:EF01:2345:6789 20
1561910404 1 1080:0:0:0:8:800:200C:417A 30
1561910404 1 1080::8:800:200C:417A 30
1561910407 1 1080::8:800:200C:417A 30
1561910408 1 FE80::9A:FE:0:0:4CA2 33
1561910408 2 FE80:0:0:9A:FE::4CA2 44 1080:0:0:0:8:800:200C:417A 10
1561910409 1 ABCD:EF01:2345:6789:ABCD:EF01:2345:6789 90
1561910412 1 2001:DB8:0:23:8:800:200C:417A 61
1561910413 1 2001:0DB8:0000:0023:0008:0800:200C:417A 65
1561910415 1 FE80::9A:FE:0:0:4CA2 66
5 100

Sample Output

1

HINT



样例的 Botnet 包含 2001:DB8:0:23:8:800:200C:417A
"::"本身就是合法地址。
本题中连续的55秒是指1ts51≤ts≤5,或2ts62≤ts≤6,或……,以此类推。


Source

[Submit][Status]