P1072光影八度交织（blend）

【题目背景】

海边剧场准备重演由八段主旋律串起的舞台诗《光影八度交织》，每段旋律都对应一幅由多种光液叠成的景象。不同光液在幕前层层叠加时，最黯淡的一束会决定整幅景象的层次，调光师需要在有限经费中完成观众指定的每一幕演出。

【题目描述】

剧场中共有 $n$ 种光液。第 $i$ 种光液的光影层次为 $d_i$，每使用一个单位需要花费 $p_i$ 枚金币，并且一幕演出中至多能够使用 $l_i$ 个单位。

调光师一共需要准备 $q$ 幕演出。第 $j$ 幕演出给出预算 $g_j$，并要求使用的光液总量不少于 $r_j$ 个单位。

准备一幕演出时，调光师可以从每种光液中取出若干个单位，也可以不使用这种光液。第 $i$ 种光液的使用量不能超过 $l_i$，所有光液的总花费不能超过本幕演出的预算。各幕演出相互独立，上一幕使用过的光液不会影响下一幕。

光影层次较低的光液会遮住其他光液中更细微的变化，因此，一幕演出的交织度由其中层次最低的光液决定，也就是所有实际使用的光液中最小的 $d_i$。

对于每一幕演出，请你求出所有合法安排中最大的交织度。若不存在合法安排，输出 $-1$。

【输入格式】

从文件 $\textbf{\textit{blend.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,q$，分别表示光液种类数与演出数量。

接下来 $n$ 行，每行包含三个正整数 $d_i,p_i,l_i$，依次表示第 $i$ 种光液的光影层次、单位价格与使用量上限。

接下来 $q$ 行，每行包含两个正整数 $g_j,r_j$，依次表示一幕演出的预算与所需光液总量。

【输出格式】

输出到文件 $\textbf{\textit{blend.out}}$ 中。

对于每幕演出输出一行一个整数，表示能够得到的最大交织度。若不存在合法安排，输出 $-1$。

【样例 1 输入】

10 223 438 5 246 2 353 1 10610 278 382 3912 5102 31110 4 1127 3 2134 1146 2155 2

【样例 1 输出】

18263-143510677-1

【说明/提示】

【样例 1 解释】

在第一组测试数据的第二幕演出中，可以使用三个单位光影层次为 $6$ 的光液，共花费 $6$ 枚金币，得到的交织度为 $6$。若要求交织度至少为 $8$，则最多只能取得两个单位光液，因此答案为 $6$。

同组其余三幕演出的答案依次为 $8,-1,3$：第一幕可以恰好使用两个单位光影层次为 $8$ 的光液，第三幕的预算不足以购买三个单位，第四幕则必须使用光影层次为 $3$ 的光液才能满足总量要求。

在第二组测试数据中，三幕演出的答案依次为 $10,7,-1$。

【样例 2】

见选手目录下的 $\textbf{\textit{blend/blend2.in}}$ 和 $\textbf{\textit{blend/blend2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{blend/blend3.in}}$ 和 $\textbf{\textit{blend/blend3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{blend/blend4.in}}$ 和 $\textbf{\textit{blend/blend4.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{blend/blend5.in}}$ 和 $\textbf{\textit{blend/blend5.ans}}$。

该组样例符合测试点 $13\sim 16$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{blend/blend6.in}}$ 和 $\textbf{\textit{blend/blend6.ans}}$。

该组样例符合测试点 $17\sim 19$ 的数据范围。

【样例 7】

见选手目录下的 $\textbf{\textit{blend/blend7.in}}$ 和 $\textbf{\textit{blend/blend7.ans}}$。

该组样例符合测试点 $20\sim 25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq10$，$1\leq n,q\leq10^5$，单个测试点内 $\sum n,\sum q\leq10^5$，$1\leq d_i,p_i,l_i\leq10^5$，$1\leq g_j,r_j\leq10^{18}$。

特殊性质 A：保证所有 $p_i=1$。

特殊性质 B：保证所有 $l_i=1$，并且所有 $r_j=1$。