Tiệm bánh JOI nổi tiếng với những chiếc bánh croissant thơm ngon. Tiệm có \(N\) thợ, đánh số từ \(1\) đến \(N\). Thợ \(i\) mất đúng \(i\) phút để làm một chiếc croissant và không thể làm đồng thời nhiều chiếc.

Có \(M\) khách hàng, đánh số từ \(1\) đến \(M\), dự định đến tiệm hôm nay; khách \(j\) đặt một chiếc tại thời điểm \(T_j\). Thời điểm \(t\) nghĩa là \(t\) phút kể từ bây giờ. Nếu không nhận được bánh trong vòng \(L\) phút kể từ khi đặt, khách sẽ bỏ cuộc và rời tiệm. Vì vậy, đơn của khách \(j\) chỉ được phục vụ nếu chiếc bánh hoàn thành không muộn hơn \(T_j+L\), kể cả đúng thời điểm \(T_j+L\).

Người quản lý K dự định cho đúng một thợ làm việc hôm nay và đang cân nhắc chọn ai, bắt đầu lúc nào. Vì thợ chỉ tập trung làm bánh sau khi bắt đầu ca, họ bỏ qua mọi đơn đến sau thời điểm bắt đầu, nhưng không bỏ qua đơn đến đúng thời điểm đó. Cụ thể, thợ bắt đầu lúc \(t\) không thể phục vụ đơn của khách \(j\) có \(T_j>t\).

Có \(Q\) phương án độc lập. Phương án \(q\) cho thợ \(A_q\) bắt đầu làm việc tại thời điểm \(B_q\). Với mỗi phương án, hãy tìm số khách tối đa có thể được phục vụ. Thợ có thể chọn thứ tự làm các đơn được xem xét; thời gian chờ để bắt đầu làm chiếc đầu tiên sau khi đến nơi và để chuyển sang chiếc tiếp theo sau khi hoàn thành một chiếc được xem là \(0\).

Dữ liệu vào

Dòng đầu gồm \(N,M,L,Q\). Dòng thứ hai gồm \(T_1,T_2,\ldots,T_M\) theo thứ tự không giảm. \(Q\) dòng tiếp theo, dòng \(q\) gồm \(A_q,B_q\).

Dữ liệu ra

In \(Q\) dòng. Dòng \(q\) là số khách tối đa có thể phục vụ trong phương án \(q\).

Ràng buộc

• \(1\le N\le4\times10^{12}\), \(1\le M\le2\,000\,000\), \(1\le L\le2\times10^{12}\), \(1\le Q\le400\,000\).
• \(0\le T_j\le2\times10^{12}\) và \(T_j\le T_{j+1}\).
• \(1\le A_q\le N\), \(0\le B_q\le4\times10^{12}\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(8\) điểm: \(M\le10\), \(Q\le100\,000\).
2. \(12\) điểm: \(M\le500\), \(Q\le100\,000\).
3. \(30\) điểm: \(T_M\le B_q<T_1+L\) với mọi \(q\).
4. \(10\) điểm: \(T_M\le B_q\) với mọi \(q\).
5. \(22\) điểm: \(M\le500\,000\), \(Q\le100\,000\).
6. \(18\) điểm: không có ràng buộc thêm.

Ví dụ

4 4 6 4
0 2 3 8
2 3
1 6
3 3
4 7

3
2
2
0

20 5 12 4
1 2 4 8 10
1 12
3 10
3 11
15 10

5
4
3
0

100000 6 272273 10
5 9 209 8128 17202 50102
164 9
11 24
835 9267
2 256
2 314156
18475 142
1826 18978
44757 1
4 1646
218 44

2
2
4
3
1
2
5
0
3
2

Nguồn

JOI 2025/2026 - Chung kết, Cuộc thi 4, bài Baker.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.