Đầu tư tài chính

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_i\). 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 để đầu tư sao cho tổng lợi nhuận

là lớn nhất, với \(1 \le i_1 < i_2 < \dots < i_k \le n\).

Ngoài ra, Hùng cũng muốn biết có bao nhiêu cách chọn \(k\) ngày để đạt được tổng lợi nhuận lớn nhất đó.

Yêu cầu. Hãy tính tổng lợi nhuận lớn nhất và số cách chọn đạt được giá trị đó.

Input

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

Output

Ghi ra hai dòng:

• dòng thứ nhất là tổng lợi nhuận lớn nhất;
• dòng thứ hai là số cách chọn đạt được tổng lợi nhuận lớn nhất, lấy dư theo \(10^9 + 7\).

Input

%
5 3
2 8 6 3 3
5 2 6

Output

%
70
2

Notes

Có hai cách chọn các ngày là \((2, 3, 4)\) hoặc \((2, 3, 5)\), đều cho lợi nhuận:

Scoring

• (20%) \(n \le 10^2\), \(k = 1\).
• (40%) \(n \le 10^3\).
• (40%) \(n \le 10^5\), \(k \le 100\).