Description

On a number line, there are $N$ people, and they are all customers of the Bookworm Bodyguard Company. Customer $i$ will move from position $A_i$ to position $B_i$ at time $T_i$. Their speed is one unit of length per unit of time.

If a bodyguard and a customer are at the same position at the same time, we say that the bodyguard is protecting that customer. Suppose the bodyguard starts protecting customer $i$ at time $a$ and stops protecting at time $b$. Then the interval $[a,b]$ is called the protection time of this customer, time $a$ is called the start time of protection, and time $b$ is called the stop time of protection. Here, $a$ and $b$ do not have to be integers. In particular, if a bodyguard is at the same position at the same time with two customers, the bodyguard can protect only one customer.

A bodyguard can move freely on the number line with speed at most one unit of length per unit of time and at least staying still. When a bodyguard stops protecting one customer, they can go to another position to protect another customer. If the path length that the bodyguard walks together with customer $i$ while protecting them is $L$, then customer $i$ will pay the bodyguard $L \times C_i$ Zimbabwe dollars, at a rate of $C_i$ Zimbabwe dollars per unit length.

As the owner of the Bookworm Bodyguard Company, Bookworm holds $Q$ planned protection proposals. In proposal $j$, a bodyguard starts working at time $P_j$ from position $X_j$.

For each proposal, find the maximum total wage (in Zimbabwe dollars) that the bodyguard can earn.

Input Format

The first line contains two integers $N,Q$, representing the number of customers and the number of planned protection proposals.

The next $N$ lines each contain four integers $T_i,A_i,B_i,C_i$, describing one customer.

The next $Q$ lines each contain two integers $P_j,X_j$, describing one planned protection proposal.

Output Format

Output $Q$ lines. Each line contains one integer, representing the maximum total wage (in Zimbabwe dollars) that the bodyguard can earn for the corresponding proposal.

2 2
1 2 1 4
3 1 3 2
1 2
3 3

8
2

3 2
3 1 5 2
1 4 1 4
4 2 4 4
2 2
6 3

15
0

5 5
8 1 4 10
8 3 7 6
1 4 6 2
3 9 5 4
6 1 9 6
7 6
6 8
1 3
9 4
2 4

30
27
48
30
48

Hint

Explanation for Sample 1

• In proposal $1$, the bodyguard can earn $4+4=8$ Zimbabwe dollars in the following way.
  • Start moving from position $2$ at time $1$.
  • Protect customer $1$ from time $1$ to time $2$. The path length traveled together is $1$, so the wage is $4 \times 1=4$ Zimbabwe dollars.
  • Stay at position $1$ from time $2$ to time $3$.
  • Protect customer $2$ from time $3$ to time $5$. The path length traveled together is $2$, so the wage is $2 \times 2=4$ Zimbabwe dollars.
• In proposal $2$, the bodyguard can earn $2$ Zimbabwe dollars in the following way.
  • Start moving from position $3$ at time $3$.
  • Move from position $3$ to position $2$ from time $3$ to time $4$.
  • Protect customer $2$ from time $4$ to time $5$. The path length traveled together is $1$, so the wage is $2 \times 1=2$ Zimbabwe dollars.

Explanation for Sample 2

• In proposal $1$, the bodyguard can earn $4+1+8+2=15$ Zimbabwe dollars in the following way.
  • Start moving from position $2$ at time $2$.
  • Move from position $2$ to position $2.5$ from time $2$ to time $2.5$.
  • Protect customer $2$ from time $2.5$ to time $3.5$. The path length traveled together is $1$, so the wage is $4 \times 1=4$ Zimbabwe dollars.
  • Protect customer $1$ from time $3.5$ to time $4$. The path length traveled together is $0.5$, so the wage is $2 \times 0.5=1$ Zimbabwe dollars.
  • Protect customer $3$ from time $4$ to time $6$. The path length traveled together is $2$, so the wage is $4 \times 2=8$ Zimbabwe dollars.
  • Protect customer $1$ from time $6$ to time $7$. The path length traveled together is $1$, so the wage is $2 \times 1=2$ Zimbabwe dollars.
• In proposal $2$, no matter how the bodyguard moves, they cannot earn any wage, and can only get $0$ Zimbabwe dollars.

Constraints and Notes

This problem uses bundled subtasks.

• Subtask 1 (6 pts): $T_i,A_i,B_i,P_j,X_j \le 3000$.
• Subtask 2 (7 pts): $Q=1$.
• Subtask 3 (15 pts): $Q \le 3000$.
• Subtask 4 (20 pts): $Q \le 4 \times 10^4$.
• Subtask 5 (52 pts): No special restrictions.

For all testdata, $1 \le N \le 2800$, $1 \le Q \le 3 \times 10^6$, $1 \le T_i,A_i,B_i,C_i \le 10^9$, $A_i \ne B_i$, $C_i$ is even, and $1 \le P_j,X_j \le 10^9$.

Note

Translated from The 20th Japanese Olympiad in Informatics Spring Training Camp, Day3 B ボディーガード (Bodyguard) English version.

Translated by ChatGPT 5