Bố bạn Hùng là một nhà đầu tư trong một quỹ tài chính. Chiến lược đầu tư của bố bạn là chọn đúng ~k~ thời điểm để đầu tư chuỗi dữ liệu của thị trường gồm ~n~ ngày. Mỗi ngày có một chỉ số thị trường là ~a_i~. Bố bạn đã xây dựng một chiến lược phân bổ trọng số ~w_1, w_2, ..., w_k~ tương ứng với từng lần đầu tư. Hùng mong muốn giúp bố của mình lựa chọn ~k~ ngày khác nhau (theo đúng thứ tự thời gian) để đầu tư cho tổng lợi nhuận ~S~ đạt cao nhất có thể theo công thức: ~S = w_1 \times a_{t_1} + w_2 \times a_{t_2} + ... + w_k \times a_{t_k}~. Ngoài ra, bạn cũng muốn biết có bao nhiêu cách chọn ngày để đạt được tổng lợi nhuận lớn nhất đó.

Yêu cầu: Tìm tổng lợi nhuận lớn nhất và số cách đầu tư để đạt được tổng lợi nhuận lớn nhất đó.

Input

• Dòng đầu tiên ghi hai số nguyên dương ~n, k~ (~n \le 10^5, k \le 100, k \le n~);
• Dòng thứ hai ghi ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~);
• Dòng thứ ba ghi ~k~ số nguyên ~w_1, w_2, ..., w_k~ (~|w_i| \le 10^6~).

Output

Ghi ra hai dòng, dòng thứ nhất ghi tổng lợi nhuận lớn nhất và dòng thứ hai ghi số cách đầu tư để đạt được tổng lợi nhuận lớn nhất đó. Kết quả được lấy dư cho ~10^9 + 7~.

Sample Input 1

5 3
2 8 6 3 3
5 2 6

Sample Output 1

70
2

Giải thích: Có 2 cách chọn các ngày là: ngày thứ {2, 3, 4} hoặc ngày thứ {2, 3, 5} đều cho tổng lợi nhuận là: ~5 \times 8 + 2 \times 6 + 6 \times 3 = 40 + 12 + 18 = 70~.

Giới hạn

• 20% số test: ~0 < n \le 10^2, k = 1~;
• 40% số test: ~0 < n \le 10^3, 0 < k \le 100~;
• 40% số test: ~0 < n \le 10^5, 0 < k \le 100~.