Rie rất thích làm bánh quy. Cô đã làm \(N\) loại bánh, trong đó có \(A_i\) chiếc thuộc loại \(i\) với \(1\le i\le N\). Để bán bánh, Rie muốn đóng tất cả bánh vào các hộp, thỏa mãn hai điều kiện:

• Các chiếc bánh trong cùng một hộp phải thuộc những loại khác nhau.
• Số chiếc bánh trong mỗi hộp phải bằng một trong \(M\) số \(B_1,B_2,\ldots,B_M\).

Cho số lượng bánh từng loại và các kích thước hộp được phép, hãy xác định có thể đóng tất cả bánh vào hộp hay không. Nếu có thể, hãy đưa ra một cách đóng sử dụng ít hộp nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N
A_1 A_2 ... A_N
M
B_1 B_2 ... B_M

Dữ liệu ra

Nếu có thể đóng tất cả bánh hợp lệ, gọi \(x\) là số hộp sử dụng. Hộp thứ \(k\) có \(c_k\) chiếc, mỗi chiếc thuộc một trong các loại \(v_{k,1},v_{k,2},\ldots,v_{k,c_k}\), mỗi loại đúng một chiếc. In ra đầu ra chuẩn theo định dạng:

x
c_1 v_1,1 v_1,2 ... v_1,c_1
c_2 v_2,1 v_2,2 ... v_2,c_2
...
c_x v_x,1 v_x,2 ... v_x,c_x

\(x\) phải là số hộp nhỏ nhất có thể. Nếu có nhiều cách đóng hợp lệ với số hộp nhỏ nhất, có thể in bất kỳ cách nào.

Nếu không thể đóng tất cả bánh thỏa mãn các điều kiện, in -1.

Ràng buộc

• \(1\le N\le 15\,000\).
• \(A_i\ge 1\) với mọi \(1\le i\le N\).
• \(A_1+A_2+\cdots+A_N\le 15\,000\).
• \(1\le M\le N\).
• \(1\le B_j\le N\) với mọi \(1\le j\le M\).
• \(B_j<B_{j+1}\) với mọi \(1\le j<M\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (6 điểm): \(N\le 500\) và \(A_i=1\) với mọi \(1\le i\le N\).
• Nhóm 2 (7 điểm): \(N\le 500\) và \(M=1\).
• Nhóm 3 (12 điểm): \(A_1+A_2+\cdots+A_N\le 15\).
• Nhóm 4 (45 điểm): \(A_1+A_2+\cdots+A_N\le 500\).
• Nhóm 5 (15 điểm): \(A_1+A_2+\cdots+A_N\le 3000\).
• Nhóm 6 (15 điểm): Không có ràng buộc bổ sung.

Ví dụ

7
1 1 1 1 1 1 1
3
1 2 3

3
2 1 7
2 2 6
3 3 4 5

5
5 3 1 2 4
1
4

-1

7
5 4 4 2 1 1 1
2
2 6

7
6 1 2 3 4 5 6
2 2 1
2 3 1
2 4 1
2 7 1
2 3 2
2 3 2

Nguồn

JOI 2022/2023 Spring Training, Contest 3, 21/03/2023. Đề gốc của JCIOI; bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.