Quan niệm về may mắn và xui xẻo từ các con số đã trở thành một phần không thể thiếu trong cuộc sống, thể hiện qua những phong tục, truyền thống và các quy tắc ẩn. Với Khoa ~3, 6, 9~ được xem là những con số may mắn.

Trong ngày gặp lại Ngân – người bạn cũ của mình. Khoa muốn tặng cho Ngân ~k~ số nguyên không âm có tổng bằng với số may mắn của Ngân.

Khoa định nghĩa độ may mắn của ~k~ số chính là tổng độ may mắn của tất cả các chữ số trong ~k~ số đó. Độ may mắn của một chữ số phụ thuộc vào giá trị của chữ số đó và vị trí của nó. Cụ thể hơn, độ may mắn của một chữ số sẽ được thể hiện ở bảng sau:

Với ~F_0, F_1, F_2, F_3, F_4, F_5~ là các hằng số được cho trước. Ví dụ độ may mắn của số ~369~ là ~3 \times F_0 + 2 \times F_1 + F_2~.

Vì Khoa rất quý Ngân, nên Khoa muốn biết tổng độ may mắn tối đa của ~k~ số có tổng bằng số may mắn của Ngân. Tuy nhiên có một vấn đề là Khoa không hề biết số may mắn của Ngân là bao nhiêu? Nên anh đã đặt ra ~Q~ tình huống giả định.

Trong tình huống giả định thứ ~i~ hãy giả sử rằng ~x_i~ là số may mắn của Ngân, bạn cần cho biết độ may mắn tối đa của ~k~ số mà Khoa có thể tặng Ngân là bao nhiêu?

Input

• Dòng đầu tiên chứa số nguyên không âm ~k~ là số lượng số mà Khoa sẽ tặng Ngân.
• Dòng thứ hai chứa sáu số nguyên không âm ~F_0, F_1, F_2, F_3, F_4, F_5~.
• Dòng thứ ba chứa số nguyên không âm ~Q~ là số lượng tình huống giả định.
• ~Q~ dòng tiếp theo mỗi dòng chứa một số ~x_i~ tương ứng với số may mắn của Ngân trong giả định thứ ~i~.

Output

Gồm ~Q~ dòng:

• Dòng thứ ~i~ chứa độ may mắn lớn nhất của ~k~ số mà Khoa có thể tặng Ngân trong tình huống giả định thứ ~i~.

Constraint

• ~1 \leq k < 10^6~.
• ~1 \leq F_i \leq 10^9~.
• ~Q \le 10^6~
• ~1 \leq x_i < 10^6~

Subtask

• Subtask ~1~ (~5\%~ số điểm): ~x_i \leq 10~.
• Subtask ~2~ (~10\%~ số điểm): ~k \leq 100~ và ~Q = 1~.
• Subtask ~3~ (~30\%~ số điểm): ~Q = 1~.
• Subtask ~4~ (~40\%~ số điểm): ~k \leq 100~.
• Subtask ~5~ (~15\%~ số điểm): không có giới hạn gì thêm.

Sample Input

3
1 2 3 4 5 6
5
57
63
1313
2024
1805

Sample Output

11
8
27
38
33

Note

• Trong tình huống giả định đầu tiên Khoa sẽ tặng cho Ngân ~3~ số ~9, 9, 39~ (~9+9+39=57~).
• Thì khi đó độ may mắn sẽ là ~S = 3 \times F_0 + 3 \times F_0 + 3 \times F_0 + F_1 = 3 \times 1 + 3 \times 1 + 3 \times 1 + 3 \times 1 + 2 = 3 + 3 + 3 + 2 = 11.~
• Sẽ có những cách tặng khác, tuy nhiên thì cách tặng này là cách tặng có tổng độ may mắn lớn nhất.