#P1882. 接力赛跑

接力赛跑

题目描述

N(1N1000)N (1\le N\le 1000) 只奶牛(编号为 11NN)在进行一个特别的接力赛跑,这个比赛特别之处在于,若干只奶牛可以同时跑。

t=0t=0 时刻,牛 11 开始沿着跑道跑。

通常,牛 ii 跑完一圈需要的时间为 Li(1Li1000)L_i (1\le L_i\le 1000) 秒。当它重新越过起点线的瞬间,它会通知另外 Mi(1MiN)M_i (1\le M_i\le N) 只奶牛 Aij(1jMi)A_{ij} (1\le j\le M_i) 起跑。注意可能出现 Mi=0M_i=0 并且 AiA_i 不存在的情况。

每一只开始赛跑的奶牛,等到它回到起点时,都会通知其他奶牛起跑。可能出现多只奶牛通知同一只奶牛起跑的情况,但是每一只奶牛只愿意跑一圈,所以它被第二次叫到的时候就不愿意再跑了。

农场主希望你帮他确定总的赛跑时间(也就是从比赛开始到最后一只奶牛越过终点的时间)。

输入格式

第一行一个整数 NN,表示参赛的牛的数量。

22 行到第 N+1N+1 行:第 i+1i+1 行包含多个用空格隔开的整数:LiL_iMiM_iMiM_i 个整数 AijA_{ij}

输出格式

一个整数,表示整个比赛结束的时间。

5
4 2 2 4
3 3 1 3 4
7 1 5
4 2 3 5
1 0
14