Ở ngoại ô Rome có một tuyến đường sắt dài, xem như trục số. Có \(N\) ga được đánh số từ \(1\) đến \(N\) theo thứ tự tọa độ tăng dần; ga \(i\) ở tọa độ \(A_i\), và không có hai ga cùng tọa độ. Tàu chỉ chạy theo chiều tọa độ tăng và dừng ở mọi ga.

Mức giá của một chặng phụ thuộc vào khoảng cách \(d ≥ 1\). Cho dãy \(1=B_1<B_2<...<B_K\). Nếu \(j_{max}\) là chỉ số lớn nhất thỏa \(B_{j_{max}} ≤ d\), giá của chặng là \(j_{max}\). Ga lên và ga xuống của một chặng phải khác nhau.

Bitaro có \(Q\) hành trình. Ở hành trình \(q\), cậu đi từ ga \(l_q\) đến ga \(r_q\) với \(l_q<r_q\). Cậu có thể xuống ở bất kỳ ga trung gian nào, thanh toán chặng vừa đi, rồi lên lại tại chính ga đó; số lần xuống không bị giới hạn. Hãy tìm tổng giá nhỏ nhất cho từng hành trình.

Dữ liệu vào

Dòng đầu là \(N\). Dòng thứ hai là \(A_1,A_2,...,A_N\). Dòng tiếp theo là \(K\), sau đó là dãy \(B_1,B_2,...,B_K\). Dòng tiếp theo là \(Q\), rồi \(Q\) dòng chứa \(l_q,r_q\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(q\) là tổng giá nhỏ nhất để đi từ ga \(l_q\) đến ga \(r_q\).

Ràng buộc

• \(2 ≤ N ≤ 150000\).
• \(1 ≤ A_1<A_2<...<A_N ≤ 10^9\).
• \(1 ≤ K ≤ 20\).
• \(1=B_1<B_2<...<B_K ≤ 10^9\).
• \(1 ≤ Q ≤ 150000\).
• \(1 ≤ l_q<r_q ≤ N\).
• Mọi giá trị đầu vào là số nguyên.

Phân nhóm

1. \(8\) điểm: \(K ≤ 2\).
2. \(11\) điểm: \(N ≤ 500\).
3. \(29\) điểm: \(Q=1\).
4. \(20\) điểm: \(K ≤ 5\).
5. \(32\) điểm: không có ràng buộc thêm.

Ví dụ

8
1 3 4 5 8 9 12 14
8
1 2 5 6 7 9 10 11
3
1 5
3 5
1 7

4
2
6

10
3 6 16 19 32 40 41 53 59 78
2
1 15
1
3 10

2

10
11 13 39 42 53 54 66 69 77 83
15
1 5 13 31 40 41 52 57 59 66 70 79 97 103 115
5
1 6
2 9
1 8
2 7
3 9

6
7
6
6
4

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 2, bài Railway Trip 4.

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.