B. Рома ба тэмдэг өөрчлөлт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Рома телевиз борлуулдаг компанид ажилладаг бөгөөд өнгөрсөн жилийн санхүүгийн тайлан бэлтгэх хэрэгтэй боллоо.

Ромад компанийн орлогын жагсаалт байна. Орлогын жагсаалт нь $n$ ширхэг бүхэл тоонуудаас бүрдсэн дараалал юм. Компанийн нийт орлогыг дарааллын бүх тоонуудын нийлбэрээр тодорхойлно. Рома дарааллын хэд хэдэн тооны яг $k$ ширхэг тэмдгийг өөрчлөхөөр шийджээ. Мөн тэр нэг тооны тэмдгийг хэдэн ч удаа өөрчилж болно.

Тооны тэмдгийг өөрчлөх гэдэг нь тухайн тоог $-1$-ээр үржүүлэх үйлдэл юм.

Компанийн нийт орлого (дараалал дахь тоонуудын нийлбэр) хамгийн их байхаар өөрчлөлт хийхэд Ромад туслана уу. Яг $k$ ширхэг өөрчлөлт хийнэ гэдгийг анхаараарай.

Оролт

Эхний мөрөнд $n$ ба $k$ $(1 ≤ n, k ≤ 10^{5})$ бүхэл тоонууд байна. Эдгээр нь дараалалд хэдэн тоо байхыг болон хэдэн өөрчлөлт хийхийг илэрхийлнэ.

Хоёр дахь мөрөнд $n$ ширхэг $a_{i}$ $(|a_{i}| ≤ 10^{4})$ бүхэл тоонуудаас бүрдсэн үл буурах дараалал байна.

Тоонуудыг хооронд нь нэг зайгаар тусгаарлан бичнэ. Өгөгдсөн дараалал үл буурахаар эрэмбэлэгдсэн байхыг анхаараарай.

Гаралт

Бодлогын хариуг нэг мөрөнд хэвлэнэ. Бид яг $k$ өөрчлөлт хийсний дараа авах боломжтой хамгийн их нийт орлого.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 2
-1 -1 1
Гаралт
3
Оролт
3 1
-1 -1 1
Гаралт
1

Тэмдэглэл

Эхний жишээнд $[1, 1, 1]$ дарааллыг авах боломжтой, тиймээс нийт орлого $3$ байна.

Хоёр дахь жишээнд $[-1, 1, 1]$ дарааллыг авах боломжтой, тиймээс нийт орлого $1$ байна.

Сэтгэгдлүүдийг ачааллаж байна...