Cho một dãy số nguyên \(A\) gồm \(n\) phần tử \(a_{1},a_{2},\ldots,a_{N}.\) Gọi \(f(A)\) là giá trị của dãy con liên tiếp có tổng lớn nhất của dãy \(A.\) Ví dụ: \(A = (5, - 1,2, - 3) \rightarrow f(A) = 5 + ( - 1) + 2 = 6\).

Yêu cầu: Cho một số nguyên \(x,\) hãy tìm cách tăng mỗi phần tử trong tối đa một dãy con liên tiếp của dãy \(A\) lên \(x\) lần sao cho \(f(A)\) lớn nhất có thể.

Dữ liệu vào:

+ Dòng đầu tiên chứa số hai số nguyên \(n\) và \(x\ \left( n \geq 1,|x| \leq 100 \right);\)

+ Dòng thứ hai chứa \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{N}\ \left( \left| a_{i} \right| \leq 100 \right);\)

Kết quả: In ra kết quả bài toán là giá trị lớn nhất của \(f(A)\).

Ví dụ:

Giải thích: Ta nhân \(a_{1}\) với \(x\), tức là \(a_{1} = a_{1} \times 2 = 5 \times 2 = 10.\) Sau đó thì \(A = (10, - 2,4, - 3,2) \rightarrow f(A) = 10 + ( - 2) + 4 = 12.\)

Giới hạn:

• \(\left\lbrack \mathbf{30\%} \right\rbrack\mathbf{:N \leq 50;}\)

• \(\left\lbrack \mathbf{30\%} \right\rbrack\mathbf{:N \leq 2000;}\)

• \(\left\lbrack \mathbf{40\%} \right\rbrack\mathbf{:N \leq}\mathbf{3.10}^{\mathbf{5}}\mathbf{.}\)