JOI sống ở đất nước IOI, nổi tiếng với một hồ nước lớn. Hôm nay, một cuộc thi sưu tập dấu sẽ được tổ chức quanh hồ.

Quanh hồ có \(2N\) địa điểm cách đều nhau, được đánh số từ \(1\) đến \(2N\) theo chiều kim đồng hồ. Có \(2N\) con đường một chiều nối các địa điểm kề nhau: đường \(i\) (\(1 \le i \le 2N-1\)) đi từ địa điểm \(i\) đến địa điểm \(i+1\), còn đường \(2N\) đi từ địa điểm \(2N\) đến địa điểm \(1\). Chính giữa mỗi con đường có một trạm đóng dấu.

Có \(N\) màu dấu, được đánh số từ \(1\) đến \(N\). Trạm trên đường \(i\) có thể đóng dấu màu \(A_i\). Với mỗi màu \(j\) (\(1 \le j \le N\)), có đúng hai trạm có thể đóng dấu màu đó.

JOI mang nhiều thẻ để tham gia cuộc thi. Mỗi thẻ có hai ô để đóng dấu, một ô bên trái và một ô bên phải. Mỗi ô chứa được nhiều nhất một dấu. Ban đầu, tất cả các thẻ đều chưa có dấu.

JOI thực hiện các bước sau theo thứ tự:

1. Chọn một trong \(2N\) địa điểm làm điểm xuất phát rồi đến đó. Nếu chọn địa điểm \(i\), JOI phải trả phí tham gia là \(C_i\).
2. Trước khi bắt đầu đi quanh hồ, JOI có thể yêu cầu ban tổ chức hoán đổi hai trạm trên hai con đường kề nhau. Cụ thể, có thể đổi trạm trên đường \(2N\) với trạm trên đường \(1\), hoặc chọn \(i\) (\(2 \le i \le 2N\)) rồi đổi trạm trên đường \(i-1\) với trạm trên đường \(i\). Mỗi yêu cầu tốn chi phí \(X\) và được thực hiện ngay lập tức. JOI được đưa ra tùy ý nhiều yêu cầu, kể cả không đưa ra yêu cầu nào. Tuy nhiên, để ngăn gian lận, không được hoán đổi hai trạm nằm ở hai phía của điểm xuất phát: nếu xuất phát tại địa điểm \(1\), không được đổi trạm trên đường \(2N\) và đường \(1\); nếu xuất phát tại địa điểm \(i\) (\(2 \le i \le 2N\)), không được đổi trạm trên đường \(i-1\) và đường \(i\).
3. Sau đó, JOI xuất phát, di chuyển theo chiều kim đồng hồ, lần lượt ghé thăm cả \(2N\) trạm và kết thúc khi quay về điểm xuất phát. Tại mỗi trạm, JOI có thể đóng dấu tùy ý nhiều lần lên tùy ý nhiều thẻ. Có thể đóng dấu vào cả hai ô của một thẻ tại cùng một trạm. Tuy nhiên, trên mỗi thẻ, luôn phải đóng dấu vào ô trái trước rồi mới đến ô phải; không được đóng dấu vào ô phải khi ô trái còn trống.

JOI muốn thu thập nhiều loại thẻ đã có dấu ở cả hai ô. Ký hiệu \((a,b)\) là loại thẻ có dấu màu \(a\) ở ô trái và màu \(b\) ở ô phải. Hai thẻ \((a_1,b_1)\) và \((a_2,b_2)\) cùng loại khi và chỉ khi \(a_1=a_2\) và \(b_1=b_2\). Vì có \(N\) màu dấu nên có tất cả \(N^2\) loại thẻ đã được đóng dấu ở cả hai ô.

Để giúp JOI lập chiến lược, bạn cần trả lời \(Q\) câu hỏi độc lập. Với câu hỏi thứ \(q\) (\(1 \le q \le Q\)), hãy tìm tổng chi phí nhỏ nhất, gồm phí tham gia và chi phí hoán đổi, để khi kết thúc cuộc thi JOI có ít nhất \(K_q\) loại thẻ đã được đóng dấu ở cả hai ô. Với các ràng buộc của bài, luôn có thể đạt được yêu cầu nếu trả đủ nhiều chi phí.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N,X\).
• Dòng thứ hai chứa \(2N\) số nguyên \(A_1,A_2,\ldots,A_{2N}\).
• Dòng thứ ba chứa \(2N\) số nguyên \(C_1,C_2,\ldots,C_{2N}\).
• Dòng thứ tư chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(q\) chứa số nguyên \(K_q\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(q\) chứa tổng chi phí nhỏ nhất để JOI thu thập được ít nhất \(K_q\) loại thẻ đã được đóng dấu ở cả hai ô khi kết thúc cuộc thi.

Ràng buộc

• \(2 \le N \le 500000\).
• \(1 \le X \le 500000\).
• \((A_1,A_2,\ldots,A_{2N})\) là một hoán vị của \((1,1,2,2,\ldots,N,N)\).
• \(1 \le C_i \le 10^{18}\) với mọi \(1 \le i \le 2N\).
• \(1 \le Q \le 500000\).
• \(1 \le K_q \le N^2\) với mọi \(1 \le q \le Q\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(5\) điểm: \(N \le 4\).
2. \(20\) điểm: \(N \le 5000\), \(Q=1\), \(K_1=N^2\).
3. \(20\) điểm: \(N \le 5000\), \(Q=1\).
4. \(19\) điểm: \(N \le 5000\).
5. \(21\) điểm: \(Q=1\).
6. \(15\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3 2
1 2 2 3 1 3
6 1 4 5 4 7
2
8
9

3
4

8 1
1 2 6 1 6 3 8 4 5 5 3 4 7 2 7 8
4 5 3 6 2 9 1 4 6 3 8 5 2 9 4 7
1
64

7

9 4
4 3 5 3 8 1 5 8 1 7 6 2 4 9 6 9 2 7
12 9 4 8 7 1 20 5 8 7 4 13 5 9 10 3 7 8
6
39
81
73
79
64
52

1
18
3
10
1
1

Giới hạn

Giới hạn thời gian là \(3\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ hai. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.