Dãy số

Cho một dãy số nguyên $A$ gồm $N$ phần tử $a_1,a_2,\dots ,a_N$. Gọi $f(A)$ là tổng lớn nhất của một dãy con liên tiếp (gồm ít nhất một phần tử) của dãy $A$. Ví dụ, với $A=[5,-1,2,-3]$ thì $f(A)=5+(-1)+2=6$.

Yêu cầu: Cho một số nguyên $x$, hãy chọn tối đa một dãy con liên tiếp của $A$ và nhân mỗi phần tử trong dãy con đó với $x$ (tức là thay mỗi phần tử $a_i$ trong dãy con bằng $a_i·x$) sao cho $f(A)$ của dãy thu được đạt giá trị lớn nhất có thể. Được phép không thực hiện phép biến đổi nào.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $x$ ($1\le N\le 3·{10}^5$; $|x|\le 100$).
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$ ($|a_i|\le 100$).

Dữ liệu ra

Một số nguyên là giá trị lớn nhất có thể của $f(A)$ sau khi thực hiện không quá một phép biến đổi.

Ràng buộc

• $1\le N\le 3·{10}^5$.
• $|x|\le 100$.
• $|a_i|\le 100$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($30\%$ số test): $N\le 50$.
• Subtask 2 ($30\%$ số test): $N\le 2000$.
• Subtask 3 ($40\%$ số test): $N\le 3·{10}^5$.

Ví dụ