Одоо бид өөр нэгэн цувааны бодлого бодох гэж байна. Танд эерэг бүхэл тоо $len$ болон $n$ ширхэг бүхэл тоо $a_{1}$, $a_{2}$, ..., $a_{n}$-уудаас тогтох $a$ цуваа өгөгджээ. Өгөгдсөн цувааны 2 шинж чанарыг танилцуулъя.

• $len$ урттай $i$ байрлалаас эхлэх цувааны дурын завсрыг авч үзье. утга нь сонгогдсон завсрын модулар нийлбэр юм. Өөрөөр хэлбэл, модулар нийлбэр гэдэг нь $len$ урттай сонгогдсон завсрын бүхэл тоонуудын нийлбэрийн абсолют утга юм.

• утга нь цувааны оновчтой нийлбэр юм. Өөрөөр хэлбэл, цувааны оновчтой нийлбэр гэдэг нь цувааны $len$ урттай янз бүрийн завсруудын бүх модулар нийлбэрүүдийн хамгийн их нь юм.

Таны даалгавар бол өгөгдсөн $a$ цувааны оновчтой нийлбэрийг тооцоолох юм. Гэсэн хэдий ч, таныг тооцохоос өмнө танд $k$-аас ихгүй дараах хэлбэртэй дараалсан үйлдлүүдийг уг цуваанд хийхийг зөвшөөрсөн: нэг үйлдэл гэдэг нь $a_{i}$ цуваанаас дурын байдлаар нэг тоог сонгоод уг тоогоо -1 ээр үржүүлэх юм. Өөрөөр хэлбэл, $k$-аас ихгүй удаа та цуваанаас дурын байдлаар $a_{i}$ тоог сонгоод үүнийг $-a_{i}$-аар солих юм. Цувааны тоо бүр нь дурын тооны удаа сонгогдож болно.

Таны даалгавар бол хамгийн ихдээ $k$ удаа дээр дүрслэгдсэн үйлдлүүд хийгдсэний дараах цувааны боломжит хамгийн их оновчтой нийлбэрийг тооцоолох юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$, $len$ ($1 ≤ len ≤ n ≤ 10^{5}$) өгөгдөнө -- эдгээр нь харгалзан цувааны элементийн тоо болон цувааны сонгогдсон дэд завсрын уртыг илэрхийлнэ.

2-дахь мөрөнд $n$ бүхэл тоо $a_{1}$, $a_{2}$, ..., $a_{n}$ $(|a_{i}| ≤ 10^{9})$-уудаас тогтох дараалал өгөгдөнө -- эдгээр нь анхны цувааг илэрхийлнэ.

3-дахь мөрөнд ганц бүхэл тоо $k$ ($0 ≤ k ≤ n$) өгөгдөнө -- энэ нь зөвшөөрөгдсөн үйлдлийн хамгийн их тоог илэрхийлнэ.

Мөрөнд өгөгдөх бүх тоонууд нь зайгаар тусгаарлагдсан байна.

Гаралт

Ганц мөрөнд $k$-аас ихгүй зөвшөөрөгдсөн үйлдлийг хийсний дараах боломжит хамгийн их оновчтой нийлбэрийг хэвлэнэ.

С++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийг битгий ашиглана уу. cin, cout streams эсвэл %I64d тодорхойлогчийг ашиглахыг илүүд үзнэ үү.