Description

Little R is obsessed with making “dark cuisine”, especially mixed juice.

There are $n$ kinds of juice in the store, numbered $0,1,\cdots,n-1$. The deliciousness of juice $i$ is $d_i$, and its price per liter is $p_i$. When making mixed juice, Little R also has some special rules: in a bottle of mixed juice, juice $i$ can be added at most $l_i$ liters.

Now $m$ children come to Little R for mixed juice. They all want Little R to use the juices in the store to make a bottle of mixed juice for them. For the $j$-th child, they want the total price of the mixed juice to be no more than $g_j$, and the volume to be at least $L_j$. Under these constraints, the children also hope the deliciousness of the mixed juice is as high as possible. The deliciousness of a bottle of mixed juice equals the minimum deliciousness among all juices that participate in the mixture. Please compute the highest deliciousness each child can get.

Input Format

The first line contains two positive integers $n, m$, the number of kinds of juice and the number of children.

The next $n$ lines each contain three positive integers $d_i, p_i, l_i$, meaning the deliciousness of juice $i$ is $d_i$, its price per liter is $p_i$, and its addition limit in one bottle is $l_i$ liters.

The next $m$ lines describe all children: each line contains two positive integers $g_j, L_j$, meaning the $j$-th child can pay at most $g_j$ yuan, and wants at least $L_j$ liters of juice.

Output Format

For all children in order, output one line for each child containing an integer, the highest deliciousness of the mixed juice they can drink. If their request cannot be satisfied, output $-1$.

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

3
2
-1
1

Hint

For all testdata, it is guaranteed that $n, m \le 100000$, $1 \le d_i,p_i,l_i \le 10^5$, $1 \le g_j, L_j \le 10^{18}$.

Translated by ChatGPT 5