F-命运的齿轮_牛客挑战赛74

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

瑶桑的技能是一组联动齿轮，一共有 $n$ 个齿轮，第 $i$ 个齿轮的齿数为 $a_i$ ，第 $i$ 个齿轮的第 $j$ 个齿的攻击值为 $b_{i,j}$ 。

每个齿轮上均拥有一个指针，第 $0$ 秒时，每个齿轮均指向该齿轮的第 $1$ 个齿。

我们采用数字 $p_i$ 代表第 $i$ 个齿轮指向的齿轮的编号，即一开始 $p_i = 1$ ， $i \in [1,n]$ 。

当时间开始流逝，经过 $1$ 秒，第 $1$ 个齿轮转动一次，即 $p_1 := p_1 + 1$ 。

当第 $i$ 个齿轮旋转一圈后，第 $i + 1$ 个齿轮才转动一次，即每当 $p_i = a_i + 1$ 时， $p_i := 1$ ，且 $p_{i + 1} := p_{i+1} + 1$ 。

对于任意时刻，瑶桑的技能齿轮能产生的伤害为 $\sum_{i=1}^{n}b_{i,p_i}$ 。

现在瑶桑想要狩猎果酱，她已经获得了 $q$ 只果酱的信息，准备逐一狩猎这些果酱，对于第 $i$ 只果酱的血量为 $H_i$ ，已知该果酱外出的时间段为 $[ L_i , R_i ]$ 。现在瑶桑想要一击必杀果酱，即 $H_i \leq \sum_{i=1}^{n}b_{i,p_i}$ 。请问瑶桑至少需要等待至多少秒，才能达成一击必杀的成就。

注意，每只果酱能否击杀均为独立询问

输入描述:

第一行给定两个整数  ，，代表联动齿轮的个数，果酱的个数。

随后  行数字代表第  个齿轮的信息。

对于每一行，首先输入一个整数 ，代表第  个齿轮的齿数，随后  个整数  代表第  个齿轮的第  个齿的攻击值。 

随后  行，每行三个数字 ，， ，分别代表果酱的血量、果酱出现时间、果酱消失的时间。

数据保证 ，，，，，。

输出描述:

输出  行，每行输出一个整数代表答案，如果无法杀死果酱，请输出 -1。

示例1

输入

复制

输出

复制

5
3
-1

说明

第  只果酱出没于  血量为 。

第  秒时，此时的  数组为 ， 齿轮组造成的伤害为  点伤害

第 秒时，此时的  数组为 ，齿轮组造成的伤害为  点伤害

第 秒时，此时的  数组为 ，齿轮组造成的伤害为  点伤害

所以等待至第  秒时，瑶桑造成的伤害能够击杀第  只果酱。

第  只果酱出没于  血量为 。

第  秒时，此时的  数组为 ， 齿轮组造成的伤害为  点伤害

所以等待至第  秒时，瑶桑造成的伤害能够击杀第  只果酱。

第  只果酱出没于  血量为 。

可以发现该果酱无法一击必杀