Bodyguard

Time limit25sMemory limit2048 MB

Summary

For each query, find the maximum reward a bodyguard starting at coordinate X at time P can earn by escorting VIPs whose walks are given in space-time.

Level: Hard9 of 10
Topics: Dynamic programming, Sorting, Greedy
Solved: No attempts yet

Problem

JOI Street is a long street running from west to east. It is treated as the number line.

From now on, $N$ very important people (VIP) will come to JOI Street and walk along it. VIPs are numbered from 1 to $N$ . VIP $i$ ( $1 \le i \le N$ ) departs from coordinate $A_i$ at time $T_i$ and walks to coordinate $B_i$ at speed 1. If $A_i < B_i$ , VIP $i$ moves in the positive direction at a constant speed. If $A_i > B_i$ , VIP $i$ moves in the negative direction at a constant speed.

A bodyguard's job is to walk along JOI Street and guard the VIPs. To guard a VIP, the bodyguard must walk with the VIP for some time. A bodyguard may start guarding a VIP in the middle of the VIP's walk, or quit guarding before the VIP finishes walking. The start and end times of guarding need not be integers. However, even if several VIPs are at the same coordinate, a bodyguard can guard at most one VIP at a time.

A bodyguard can walk along JOI Street freely at a speed of at most 1 per unit time. After finishing guarding a VIP, the bodyguard may move to another place and start guarding another VIP. If a bodyguard walks with VIP $i$ , the VIP pays the bodyguard $C_i$ yen per unit distance, measured over the distance the bodyguard guards the VIP. It is guaranteed that $C_i$ is an even integer.

You work for a security company and plan $Q$ projects to guard the VIPs. Projects are numbered from 1 to $Q$ . In project $j$ ( $1 \le j \le Q$ ), a bodyguard starts working at coordinate $X_j$ at time $P_j$ . For each project, compute the maximum total reward. Under the constraints of this task, the maximum total reward of a project is always an integer.

Input

Read the following data from standard input. All given values are integers.

N Q
T1 A1 B1 C1
.
.
.
TN AN BN CN
P1 X1
.
.
.
PQ XQ

Output

Write $Q$ lines to standard output. The $j$ -th line contains the maximum total reward for project $j$ , as an integer.

Constraints

$1 \le N \le 2800$
$1 \le Q \le 3000000$
$1 \le T_i \le 10^9$ ( $1 \le i \le N$ )
$1 \le A_i \le 10^9$ ( $1 \le i \le N$ )
$1 \le B_i \le 10^9$ ( $1 \le i \le N$ )
$A_i \ne B_i$ ( $1 \le i \le N$ )
$1 \le C_i \le 10^9$ ( $1 \le i \le N$ )
$C_i$ is an even integer ( $1 \le i \le N$ )
$1 \le P_j \le 10^9$ ( $1 \le j \le Q$ )
$1 \le X_j \le 10^9$ ( $1 \le j \le Q$ )

Examples2

Example 1
Input
```
2 2
1 2 1 4
3 1 3 2
1 2
3 3
```
Expected output
```
8
2
```

Example 2

Input

Expected output

15
0