Delicious Mixed Fruit Juice

Little R is fond of preparing "dark cuisine", especially mixed fruit juices. There are \(n\) kinds of juices in the store, labeled \(0,1,\dots,n-1\). The \(i\)th juice has a taste value \(d_i\) and costs \(p_i\) per liter. However, when preparing a mixed juice, there is an additional restriction: at most \(l_i\) liters of the \(i\)th juice can be used in one bottle.

Now, \(m\) children come to Little R. The \(j\)th child requires a bottle of mixed juice with a total price not exceeding \(g_j\) and with a volume of at least \(L_j\) liters. Under these restrictions, the children wish the juice to be as delicious as possible. The taste of a bottle of mixed juice is defined as the minimum taste value among all juices used (i.e. those with a nonzero volume in the mix). For each child, your task is to compute the maximum achievable taste of the mixed juice that meets the requirements. If it is impossible to prepare a juice satisfying the conditions, output -1.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input begins with two integers \(n\) and \(m\) (the number of juices and the number of children).

Then \(n\) lines follow. Each of these lines contains three integers \(d_i\), \(p_i\), and \(l_i\) representing the taste value, price per liter, and the maximum allowable liters for the \(i\)th juice.

After that, \(m\) lines follow, each containing two integers \(g_j\) and \(L_j\), representing the maximum total price and the minimum required volume for the \(j\)th child.

outputFormat

For each query (child), output a single line containing the maximum achievable taste of the mixed juice that meets the requirements. If it is impossible to satisfy the conditions for a query, output -1.

sample

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

3
-1
5