Phố JOI là một con phố dài theo hướng tây - đông, được xem là trục số.

Sắp tới, \(N\) nhân vật quan trọng (VIP), đánh số từ \(1\) đến \(N\), sẽ đi bộ trên phố. VIP \(i\) xuất phát từ tọa độ \(A_i\) vào thời điểm \(T_i\) và đi đến tọa độ \(B_i\) với tốc độ \(1\) đơn vị khoảng cách mỗi đơn vị thời gian. Nếu \(A_i<B_i\), người đó đi theo chiều dương với tốc độ không đổi; nếu \(A_i>B_i\), người đó đi theo chiều âm với tốc độ không đổi.

Công việc của vệ sĩ là đi trên phố và bảo vệ các VIP. Để bảo vệ một VIP, vệ sĩ phải đi cùng người đó trong một khoảng thời gian. Có thể bắt đầu bảo vệ giữa hành trình hoặc ngừng trước khi VIP đến đích. Thời điểm bắt đầu hoặc kết thúc bảo vệ không nhất thiết là số nguyên. Tuy nhiên, kể cả khi nhiều VIP ở cùng tọa độ, một vệ sĩ chỉ có thể bảo vệ tối đa một VIP tại một thời điểm.

Vệ sĩ có thể tự do di chuyển trên phố với tốc độ không quá \(1\). Sau khi bảo vệ một VIP, vệ sĩ được phép di chuyển đến nơi khác rồi bảo vệ VIP khác. Khi đi cùng VIP \(i\), vệ sĩ nhận \(C_i\) yên cho mỗi đơn vị khoảng cách đã bảo vệ người đó. Bảo đảm \(C_i\) là số nguyên chẵn.

Bạn làm việc tại một công ty bảo vệ và đang lên \(Q\) kế hoạch, đánh số từ \(1\) đến \(Q\). Trong kế hoạch \(j\), một vệ sĩ bắt đầu làm việc tại tọa độ \(X_j\) vào thời điểm \(P_j\). Hãy tính tổng thù lao lớn nhất có thể nhận được cho từng kế hoạch.

Với các ràng buộc của bài, có thể chứng minh rằng tổng thù lao lớn nhất của mỗi kế hoạch luôn là số nguyên.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Mọi giá trị đều là số nguyên.

N Q
T_1 A_1 B_1 C_1
...
T_N A_N B_N C_N
P_1 X_1
...
P_Q X_Q

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) (\(1\le j\le Q\)) chứa số nguyên là tổng thù lao lớn nhất của kế hoạch \(j\).

Ràng buộc

• \(1\le N\le2800\).
• \(1\le Q\le3000000\).
• \(1\le T_i,A_i,B_i,C_i\le10^9\) với mọi \(1\le i\le N\).
• \(A_i\ne B_i\) với mọi \(1\le i\le N\).
• \(C_i\) là số nguyên chẵn với mọi \(1\le i\le N\).
• \(1\le P_j,X_j\le10^9\) với mọi \(1\le j\le Q\).

Phân nhóm

• Nhóm 1 (6 điểm): \(T_i,A_i,B_i\le3000\) với mọi \(1\le i\le N\); \(P_j,X_j\le3000\) với mọi \(1\le j\le Q\).
• Nhóm 2 (7 điểm): \(Q=1\).
• Nhóm 3 (15 điểm): \(Q\le3000\).
• Nhóm 4 (20 điểm): \(Q\le40000\).
• Nhóm 5 (52 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 3. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.