工厂有一条生产配件的生产线,专门为工厂的某型号的汽车生产配件。
该生产线每次可以生产 N 个配件,配件的编号为 1 \sim N,生产配件的顺序也严格按照 1 \sim N 的顺序进行。
生产线生产一个配件需要 1 小时,每小时只能生产 1 个配件。某些编号的配件,在生产时,要使用一些其他配件作为辅助。每个配件生产出来之后,需要经过 3 个小时的完全冷却,才能在下一个小时作为其他配件的加工辅助。由于配件生产顺序严格按照 1 \sim N,因此如果 X 号配件需要 Y 号配件辅助,可以确保 X \gt Y。
比如:如果要生产 2 个配件,编号分别为 1,2,如果 2 号配件不需要 1 号配件辅助,那么两个配件生产完毕共需 2 小时。如果 2 号配件需要 1 号配件的辅助,那么在第 1 小时结束,1 号配件生产完毕,需要额外增加 3 个小时的冷却时间,因此 2 号配件需要在第 5 个小时结束才能被生产出来,两个配件生产完需要 5 小时,产生了额外的 3 小时的冷却时间。
再比如:如果要生产 5 个配件,只有编号为 5 的配件需要编号为 1 的配件辅助,总生产时间还是 5 小时,因为生产 5 号配件时,1 号配件已经冷却完毕,不需要产生额外的冷却时间。
现给出每个配件生产需要其他哪些配件辅助的所有数据,请问 N 个配件生产完毕,一共产生了多少小时的额外冷却时间?
第 1 行读入一个整数 N,代表配件总数。
接下来 N 行,每行有 3 个整数,如果接下来第 i 行的第 j 个整数为 1 ,表示配件 i 生产时,需要配件 i-j 的辅助。
测试数据确保不会出现 i \le j 时, 第 i 行第 j 列的值为 1 的情况。
输出一个整数,代表 N 个配件生产完毕,一共产生了多少小时的额外冷却时间。
3 0 0 0 1 0 0 1 1 0
6
3 0 0 0 1 0 0 0 1 0
3
8 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1
8
第 1 行读入 N=3。
接下来的 3 行:
第 2 行第 1 个整数为 1,说明 2 号配件需要 2-1=1 号配件的辅助。
第 3 行前 2 个整数为 1,说明 3 号配件需要 3-1=2 号和 3-2=1 号配件的辅助。
因此每个小时生产线的工作记录如下:
第 1 个小时,生产 1 号配件。
第 2 \sim 4 个小时,等待 1 号配件冷却。
第 5 个小时,生产 2 号配件。
第 6 \sim 8 个小时,等待 2 号配件冷却。
第 9 个小时生产 3 号配件。
一共产生了 6 小时的额外冷却时间。
对于 20\% 的数据,1 \le N \le 20,测试数据只有一个配件要使用其他配件作为生产辅助的情况。
对于 100\% 的数据, 1 \le N \le 100。