Minh có điểm thi tốt trong kỳ thi chọn HSG tỉnh. Thầy giáo của Minh có \(n\) gói quà. Gói quà thứ \(i\) có giá trị là \(g_i (1 \le g_i \le 1000)\). Thầy cho Minh chọn quà. Minh được phép chọn nguyên gói quà hoặc một phần của gói quà. Trong trường hợp chọn một phần của gói quà thứ \(i\), gói quà \(i\) được chia thành \(k\) phần có giá trị bằng nhau (\(k\) là một số nguyên tố, \(k \le g_i\); \(g_i\) chia hết cho \(k\)) thì Minh chỉ được chọn một phần. Vì còn phải để giành quà để chia cho các bạn nên Minh được chọn các gói quà (kể cả một phần của gói quà) có tổng giá trị không quá \(S\) \((0 \le S \le 10^6)\). Minh muốn chọn quà có giá trị lớn nhất.

Ví dụ: Với \(n = 3\), giá trị các quà là \(5, 24, 9\) và \(S = 15\). Tổng \(S\) có thể đạt được sau hai lần chia: 24 ÷ 2 + 9 ÷ 3 = 15.

Yêu cầu

• Cho biết \(n, g_i\) \((i = 1..n)\) và \(S\). Hãy giúp Minh chọn quà sao cho có tổng giá trị quà lớn nhất thể và với số lần chia tối thiểu cần thực hiện để được giá trị quà lớn nhất.

Dữ liệu vào

• Gồm nhiều bộ dữ liệu (số bộ dữ liệu không quá \(10^3\)), mỗi bộ dữ liệu trên một nhóm \(3\) dòng:
• Dòng thứ nhất: chứa số nguyên \(n\).
• Dòng thứ hai: chứa \(n\) số nguyên \(g_1, g_2, ..., g_n\).
• Dòng thứ ba: chứa số nguyên \(S\).

Dữ liệu ra

• Ứng với mỗi bộ dữ liệu là một dòng chứa \(2\) số \(D\) (tổng giá trị quà) và \(C\) (số lần chia tối thiểu) tìm được theo yêu cầu.

Ràng buộc:

• Các test tương ứng với 50% số điểm: có \(n \le 10\); các số \(g_i\) đều là số nguyên tố.
• Các test tương ứng với 25% số điểm: có \(n \le 100\) và số bộ dữ liệu là \(1\).
• Các test tương ứng với 25% số điểm: có \(n \le 100\).

Input 1

3  
5 24 9  
15  
2  
210 1000  
1081

Output 1

15 2  
1070 1