Cho một mảng ~A~ gồm ~n~ số nguyên và một số nguyên ~k~. Bạn cần tìm mảng con tăng dần có độ dài chính xác ~k~ sao cho:

1. Các phần tử trong mảng con phải tăng dần nghiêm ngặt ~(A[i] < A[i + 1])~.
2. Tổng của mảng con phải chia hết cho ~k~.
3. Nếu có nhiều mảng con thỏa mãn, chọn mảng con có tổng lớn nhất.

Nếu không tồn tại mảng con nào thỏa mãn điều kiện, in ra -1.

Note: Giả sử Input chỉ có một Testcase duy nhất.

Input Specification

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \le k \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \dots, A_n~ ~(-10^9 \le A_i \le 10^9)~.

Output Specification

• In ra một số nguyên duy nhất: tổng của mảng con tối ưu thỏa mãn điều kiện, hoặc -1 nếu không tồn tại.

Constrains

• ~1 \le k \le n \le 10^5~.
• ~-10^9 \le A_i \le 10^9~.

Sample Cases

Input #1:

6 3
1 2 3 4 5 6

Output #1:

9

Explanation #1:

Mảng con ~[2, 3, 4]~ tăng dần, có độ dài ~3~, và tổng ~9~ chia hết cho ~3~. Đây là mảng con tối ưu.

Input #2:

5 2
5 4 3 2 1

Output #2:

-1

Explanation #2:

Không có mảng con tăng dần nào có độ dài ~2~ vì mảng giảm dần.

Input #3:

7 4
1 3 5 7 2 4 6

Output #3:

18

Explanation #3:

Mảng con ~[1, 3, 5, 7]~ tăng dần, có độ dài ~4~, và tổng ~16~ chia hết cho ~4~. Nhưng mảng con ~[2, 4, 6, 8]~ có tổng ~20~ cũng chia hết cho ~4~ và lớn hơn.