Đầu tư tài chính

Tệp đầu vào: INVP.INP
Tệp đầu ra: INVP.OUT

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ư 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_t~. Bố bạn đã xây dựng một chiến lược phân bổ trọng số ~w_1, w_2, \dots, 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 ~i_1 < i_2 < \dots < i_k~) để đầu tư sao cho tổng lợi nhuận ~S~ đạt cao nhất có thể theo công thức:

~S = w_1 \times a_{i_1} + w_2 \times a_{i_2} + \dots + w_k \times a_{i_k}~

Ngoài ra, bạn ấy 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 đó.

Em hãy viết chương trình giúp bạn Hùng giải quyết mong muốn trên.

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

Dữ liệu vào:

Từ tệp văn bản INVP.INP gồm:

• 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 ~a_1, a_2, \dots, a_n~ (~|a_t| \le 10^9~) là chỉ số thị trường mỗi ngày;
• Dòng thứ ba ghi ~k~ số nguyên ~w_1, w_2, \dots, w_k~ (~|w_t| \le 10^6~) là trọng số đầu tư.

Kết quả:

Ghi ra tệp văn bản INVP.OUT gồm hai dòng:

• Dòng thứ nhất ghi tổng lợi nhuận lớn nhất;
• Dòng thứ hai ghi số cách đầu tư để đạt được tổng lợi nhuận lớn nhất đó (chia lấy dư cho ~10^9 + 7~).

Ví dụ:

Ví dụ 1
Sample Input

5 3
2 8 6 3 3
5 2 6

Sample Output

70
2

Giải thích:

Có 2 cách chọn các ngày là: chọn ngày thứ (2, 3, 4) hoặc ngày thứ (2, 3, 5) đều cho tổng lợi nhuận lớn nhất 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~.