T512573 绿钥匙

**本题数据已于约 `11:30` 修正** 在一些魔塔中，持有绿钥匙的数量可以反映咸鱼的程度。通常，拿取绿钥匙或全都能提升难度，或全都能降低难度。 但这座塔不一样，拿取一把绿钥匙可能提升难度，也可能降低难度。现在你不需要拆塔，只需根据现有条件，找出一定限制下的最优局面。

给出魔塔的楼层数，你进入魔塔前的生命值，进入每层的代价，该层是否有一把绿钥匙，获取这把绿钥匙的代价。 你初始在 $0$ 层，你必须依次到达更高的楼层 $(1,2,3\dots)$ 。每次到达一个新的楼层，你的生命值会减去进入这层的代价。 你可以在任意时刻内取得已到达楼层中的一把绿钥匙，并将生命值减去获取这把绿钥匙的代价。 你的生命值必须始终大于零。 给出一些询问，每次询问在最高到达楼层数在 $[l_1,r_1]$ 之间，取得绿钥匙数量在 $[l_2,r_2]$ 之间时，你最大的生命值。或者输出无解。

第一行三个正整数 $n,m,t$，依次表示层数，初始生命值，询问数。 接下来 $n$ 行，每行先是两个**整数** $c，b$ ，第一个数表示进入这层的代价，第二个数表示这层是否有一把绿钥匙（ $1$ 为有，$0$ 为无）。如果这层有一把绿钥匙，再输入一个**整数** $g$ ，表示获取这把绿钥匙的代价。 接下来 $T$ 行，每行四个**正整数** $l_1,r_1,l_2,r_2$，表示楼层数和绿钥匙数的限制。

对于每个询问，如果有解，输出一行一个正整数，表示最大剩余的生命值；如果无解，则输出 $-1$。

子任务一（ $20pts$ ）：$1\le n\le10,1\le t\le10^3$。 子任务二（ $40pts$ ）：$1\le n\le100,1\le t\le10^4$。 子任务三（ $40pts$ ）：$1\le n\le10^3,1\le t\le10^5$。 对于所有数据，满足 $-10^9\le m,c,g\le10^9$，$1\le l_1 \le r_1 \le n，1\le l_2 \le r_2 \le n,b\in\{0,1\}$。