보디가드

JOI 거리는 서쪽에서 동쪽으로 뻗은 긴 길이며, 수직선으로 본다.

지금부터 $N$명의 매우 중요한 인물(VIP)이 JOI 거리에 와서 이 길을 걷는다. VIP에게는 1부터 $N$까지 번호가 붙는다. VIP $i$ ($1 \le i \le N$)는 시각 $T_i$에 좌표 $A_i$에서 출발하여 좌표 $B_i$까지 걷는다. 속력은 단위 시간당 1이다. $A_i < B_i$이면 VIP $i$는 양의 방향으로 일정한 속력으로 움직이고, $A_i > B_i$이면 음의 방향으로 일정한 속력으로 움직인다.

경호원의 일은 JOI 거리를 걸으며 VIP를 경호하는 것이다. VIP를 경호하려면 일정 시간 동안 그 VIP와 함께 걸어야 한다. 경호원은 VIP가 걷는 도중에 경호를 시작할 수 있고, VIP가 걷기를 마치기 전에 경호를 그만둘 수도 있다. 경호를 시작하고 끝내는 시각은 정수가 아니어도 된다. 다만 여러 VIP가 같은 좌표에 있더라도, 경호원이 동시에 경호할 수 있는 VIP는 한 명뿐이다.

경호원은 최대 속력 단위 시간당 1로 JOI 거리를 자유롭게 걸을 수 있다. VIP 한 명의 경호를 마치면 다른 곳으로 이동해 다른 VIP의 경호를 시작해도 된다. 경호원이 VIP $i$와 함께 걸으면, VIP는 경호한 거리 1 단위당 $C_i$엔을 경호원에게 준다. $C_i$는 짝수 정수임이 보장된다.

여러분은 보안 회사에서 일하며 VIP를 경호하는 프로젝트 $Q$개를 계획한다. 프로젝트에는 1부터 $Q$까지 번호가 붙는다. 프로젝트 $j$ ($1 \le j \le Q$)에서 경호원은 시각 $P_j$에 좌표 $X_j$에서 일을 시작한다. 각 프로젝트마다 받을 수 있는 보상 총합의 최댓값을 구하라. 이 문제의 제약 아래에서 프로젝트의 보상 총합 최댓값은 항상 정수임이 증명되어 있다.

다음 형식으로 표준 입력에서 데이터를 읽는다. 주어지는 모든 값은 정수이다.

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

표준 출력에 $Q$개의 줄을 쓴다. $j$번째 줄에는 프로젝트 $j$의 보상 총합 최댓값을 정수로 출력한다.

• $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$는 짝수 정수이다 ($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$)