Migrated from Lutece 2952 新型背包

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小Y有一个新型背包，背包里可以收集一些奇异的元素。

之所以说元素是奇异的，是因为每个元素都有三个属性：“单位体积价值”“体积”“奇异值”。注意，每一个元素可以视为可拆分的，即若有 $5$ 体积的元素，你可以取其中的任意 $1,2,3,4,5$ 体积装入背包，但不论如何拆分，该元素的“奇异值”不变，只会影响其总价值。

之所以说这个背包是新型的，是因为背包可以根据其中装载的元素给出一个“装载奇异值”，我们定义“装载奇异值”为背包内所有物品的”奇异值“的最小值。

现在小Y列出了他所拥有的的所有的 $n$ 个奇异元素的属性，同时他也试图找到一种限定条件下的最优装载方式：每一次小Y会给你两个限定值 $V, \ C$，表示小Y这一次希望装进背包的元素的价值总和不超过 $V$，同时至少要在背包里装入 $C$ 体积的元素，在这样的限定条件下，小Y想知道怎样最大化背包装载元素的“装载奇异值”。

你只需要计算出最大的“装载奇异值”的数值即可，不需要输出具体方案。当然，对于一些不存在答案的限制，请你输出 $-1$，表示答案不存在。

Input

输入第一行包含两个正整数 $n, m$，表示元素的种数和询问的数量。接下来 $n$ 行，每行三个正整数 $s_i, p_i, v_i$，表示 $i$ 号元素的奇异值为 $s_i$，单位体积价值为 $p_i$，一共有 $v_i$ 的体积。

接下来 $m$ 行依次描述所有询问：每行两个数正整数 $V_j, C_j$ 描述一个询问，表示小 Y 最多能装载 $V_j$ 元钱的总价值，他想要至少装 $C_j$ 体积的元素。

Output

对于所有的询问分别输出一行。每行一个整数，表示最大“装载奇异值”的数值，若不存在解，则输出 $-1$

Samples

3 4
1 3 5
2 1 3
3 2 5
6 3
5 3
10 10
20 10

3
2
-1
1

Constraints

保证 $1\leq n, m \le 100000, \ 1 \le s_i, p_i, v_i \le 10^5，1 \le V_j, C_j \le 10^{18}$。

Resources

2023 UESTC ICPC Training for Data Structures