Cho một dãy \(a\) độ dài \(n\) gồm các số nguyên. Dãy \(a\) bị biến đổi để lặp lại \(k\) lần, nghĩa là dãy \(a\) thoả mãn \(a_i=a_{i-n}\) (với mọi \(n<i\le n*k\)), và độ dài \(a\) sẽ thành \(n*k\). Hãy tìm đoạn con liên tiếp có tổng lớn nhất trong dãy \(a\) sau khi biến đổi và in ra tổng lớn nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n,k\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1,a_2,a_3,...,a_n\)
• \(n\le 10^6; k\le 10^6; |a_i|\le 1000\)

Output

• Dòng duy nhất là tổng của đoạn con liên tiếp có tổng lớn nhất.

Example

5 2
2 7 -2 3 -5

15