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 để dà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: ~\frac{24}{2} + \frac{9}{3} = 15~.

Cho biết ~n~, ~g_i~ (~i = 1 \dots 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

File gồm nhiều bộ dữ liệu (số bộ dữ liệu không quá ~10^3~; không có dòng nào cho biết số bộ, đọc cho đến hết file), mỗi bộ dữ liệu cho 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, \dots, g_n~.
• Dòng thứ ba: chứa số nguyên ~S~.

Kết quả

Tương ứ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.

Ví dụ

QUA.INP

3
5 24 9
15
2
210 1000
1081

QUA.OUT

15 2
1070 1

Giới hạn

• Subtask 1 (50% số điểm): ~n \le 10~; các số ~g_i~ đều là số nguyên tố.
• Subtask 2 (25% số điểm): ~n \le 100~ và số bộ dữ liệu là 1.
• Subtask 3 (25% số điểm): ~n \le 100~.