Dãy đẹp

Cho dãy $A = (a_1, a_2, \dots, a_N)$. Độ đẹp của dãy $A$ được định nghĩa là tổng lớn nhất của một đoạn con liên tiếp (có thể rỗng) của dãy. Chẳng hạn, dãy $A = (-3, 8, 4, -2, 12)$ có độ đẹp bằng $22$ (đoạn con $(8, 4, -2, 12)$), dãy $B = (-1, -2, -3, -4, -5)$ có độ đẹp bằng $0$ (đoạn con rỗng).
Để gia tăng độ đẹp của dãy $A$, bạn được phép chọn tối đa một đoạn con liên tiếp của dãy và nhân từng phần tử trong đoạn con đó lên $X$ lần. Xác định độ đẹp lớn nhất có thể đạt được của dãy.

Dữ liệu (nhập từ bàn phím/thiết bị vào chuẩn)

• Dòng 1: hai số nguyên $N, X$ ($1 \le N \le 4.10^5;\ -100 \le X \le 100$);
• Dòng 2: $N$ số nguyên $a_1, a_2, \dots, a_N$ ($|a_i| \le 10^9$).

Kết quả (ghi ra màn hình/thiết bị ra chuẩn)

• Dòng 1: số nguyên là độ đẹp tối đa của dãy $A$ sau khi thực hiện không quá một thao tác nói trên.

1. 20% điểm dành cho các test có $1 \le N \le 50$;
2. 30% điểm khác dành cho các test có $1 \le N \le 300$;
3. 20% điểm khác dành cho các test có: $a_i \ge 0\ \forall i$;
4. 30% điểm còn lại không có ràng buộc bổ sung.