Maximum Guard Wage

A guard company has a set of N customers on an infinite number line. For each customer i, at time \(T_i\) the customer starts moving from position \(A_i\) to position \(B_i\) at a constant speed of 1 unit per time unit (so that the journey lasts \(|B_i-A_i|\) time units, and the customer finishes at time \(T_i+|B_i-A_i|\)). When a guard is at the same position at the same time as a customer, the guard is considered to be protecting that customer. A guard may only protect one customer at any given moment even if more than one customer is present.

When a guard starts protecting customer i at time \(a\) and stops at time \(b\) (\(a\) and \(b\) may be non‐integers), the protected distance is \(L = b-a\). Customer i will pay the guard \(L\times C_i\) (in Zimbabwe dollars), where \(C_i\) is a given constant for customer i.

The guard can move arbitrarily on the line subject to a speed limit of 1 unit per time unit (or can stay stationary). When switching from protecting one customer to another, the guard may reposition freely (subject to the movement limit) to begin protecting the new customer.

You are given Q scenarios. In the j-th scenario, a single guard starts working at time \(P_j\) from position \(X_j\). The guard may choose to protect some customers and earn wages according to the following rule. If the guard chooses to protect a customer i, then it is optimal to intercept the customer as early as possible. In other words, if the guard (currently at time \(t_0\) at position x) attempts to protect customer i, then he moves to customer i's starting position \(A_i\) and intercepts the customer at time:

[ \tau_i=\max\Bigl(T_i,, t_0+|A_i-x|\Bigr). ]

If \(\tau_i\le T_i+|B_i-A_i|\), the guard can fully protect customer i from time \(\tau_i\) until the customer finishes moving at time \(T_i+|B_i-A_i|\), earning a wage of

[ \text{wage}_i = \bigl(T_i+|B_i-A_i|-\tau_i\bigr)\times C_i. ]

After protecting customer i, the guard will be at position \(B_i\) at time \(T_i+|B_i-A_i|\) and may then go on to protect another customer j (with \(T_j\)) provided that the guard can get there in time. That is, if from state \((t_0,x)=(T_i+|B_i-A_i|,B_i)\) we have

[ \max\Bigl(T_j,, T_i+|B_i-A_i|+|A_j-B_i|\Bigr)\le T_j+|B_j-A_j|, ]

then the guard may protect customer j earning an extra wage of

[ \text{wage}_j = \bigl(T_j+|B_j-A_j|-\max\bigl(T_j, T_i+|B_i-A_i|+|A_j-B_i|\bigr)\bigr)\times C_j. ]

</p>

The guard cannot protect customers partially in segments; whenever he chooses to protect a customer he does so in a contiguous time interval from his time of interception until the customer finishes. Determine, for each scenario, the maximum total wage (in Zimbabwe dollars) the guard can earn by choosing an optimal sequence of customers to protect.

inputFormat

The input begins with two integers N and Q on one line:

• \(1 \le N \le \text{(small)}\) is the number of customers.
• \(1 \le Q \le \text{(small)}\) is the number of scenarios.

Then follow N lines, each containing four integers:

[ T_i; A_i; B_i; C_i ]

For each customer \(i\):

• \(T_i\) is the starting time when customer \(i\) begins moving.
• \(A_i\) is the starting position, and \(B_i\) is the ending position (\(|B_i-A_i|\) is the total distance traveled).
• \(C_i\) is the wage per unit distance.

Then follow Q lines, each with two integers:

[ P_j; X_j ]

For the j-th scenario, a guard starts at time \(P_j\) at position \(X_j\).

outputFormat

For each scenario, output one line containing a single integer: the maximum total wage the guard can earn.

sample

2 2
1 1 4 1
2 3 5 2
0 0
1 2

3
4

</p>