任务四:挑战模式。其实吧,挑战模式T^T已经做好了,并不需要你来完成,但是T^T想知道模块的开启条件是否设定得合理,因此T^T想知道挑战模式的模块的开启成本是怎样的。
挑战模式中一个知识点是一个模块,一个模块内有若干题目(假定有无穷多的题目),在这个模块做成一题,可以给对应模块增加1积分。
在做某模块之前,首先要开启这个模块,开启模块有若干个条件。每个条件的格式是“在某个模块中获得x积分”。要开启模块,必须同时满足所有条件,条件数是0的模块是默认开启的。
给定模块和条件,你的任务是计算开启某模块至少需要做多少道题目。
(挑战模式的设计初衷是给新手们入门,以及可以在集训队教学之前自己学习对应知识。有能力的人最好进度超前啦。听课的时候就能一遍听懂了~)
输入多组数据。每组数据格式如下:
第一行是一个n表示模块的总数。(1<=n<=1000)
接下来有n块结构相同的输入,第i块表示第i个模块的情况(i>=1)。每个模块的说明如下
第一行是一个数字mi。表示第i个模块有mi个条件。(0<=mi<i)
然后是mi行,每行是两个整数x,y,表示开启第i个模块的条件是在第x个模块中获得y分。(同一个模块的条件中所有的x是互不相同的)(1<=x<i 、 1<=y<=100)
接下来是一个q表示询问的次数(1<=q<=n)
然后跟着q行,每行是一个整数qi表示询问开启第i个模块至少需要做多少题。
注意:
1、模块编号从1开始
2、大数据不超过2组,且大数据的总询问次数不超过100次
3、条件中可能有重复的模块,取最高(如模块A有2个条件,分别是“在模块B中获得x分”和“在模块B中获得y分”,此时x和y中较小的那个即无效)
4、由于挑战模式的所有模块都必须能够达到,所有条件“开启A前要在模块B中获得x分”中的A均大于B。(数据范围也有体现。)
每组样例输出一行,格式是“Case #x: y”。x表示询问的序号数(从1开始),y表示答案,如果不可能开启这个模块,则y输出-1。
3 0 1 1 5 2 1 3 2 5 3 1 2 3 1 0 1 1
Case #1: 0 Case #2: 5 Case #3: 10 Case #4: 0