Final test: Đầu tư tài chính

Yêu cầu: Cho mảng ~A~ gồm ~N~ ngày, mỗi ngày có chỉ số thị trường ~a_i~. Cho mảng trọng số ~W~ gồm ~K~ phần tử ~w_1, w_2, ..., w_K~. Hãy chọn ra đúng ~K~ ngày khác nhau theo thứ tự thời gian ~i_1 < i_2 < \dots < i_K~ để đầu tư sao cho tổng lợi nhuận ~S = w_1 \times a_{i_1} + w_2 \times a_{i_2} + \dots + w_K \times a_{i_K}~ đạt mức lớn nhất. Đồng thời đếm số cách chọn để đạt được mức lợi nhuận lớn nhất đó (kết quả đếm lấy dư cho ~10^9 + 7~).

Giới hạn:

• ~1 \le k \le n \le 10^5~
• ~1 \le k \le 100~
• ~|a_i| \le 10^9~, ~|w_i| \le 10^6~
• Thời gian: 1.0s | Bộ nhớ: 256 MB

Dữ liệu vào (INVP.INP):

• Dòng 1: Hai số nguyên ~N~ và ~K~.
• Dòng 2: ~N~ số nguyên biểu diễn mảng ~A~.
• Dòng 3: ~K~ số nguyên biểu diễn mảng ~W~.

Kết quả (INVP.OUT):

• Dòng 1: Tổng lợi nhuận lớn nhất.
• Dòng 2: Số cách đầu tư đạt lợi nhuận lớn nhất modulo ~10^9 + 7~.

Ví dụ:

Input:

5 3
2 8 6 3 3
5 2 6

Output:

70
2