C. Бэлэг

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

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

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

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

Бяцхан минж програмын эхлэн суралцагч, учир нь мэдээлэл зүй бол түүний дуртай хичээл. Удахгүй мэдээлэл зүйн багш нь тѳрсѳн ѳдрѳѳ тэмдэглэх бѳгѳѳд минж түүнд бэлэг бэлдэхээр шийджээ. Тэрээр цонхны тавцан дээрээ $n$ цэцэг тарьж байгаа ба тэднийг ургаж томрохыг хүлээж байна. Гэсэн хэдий ч эдгээр цэцэгнүүд нь услахгүй л бол ургадаггүй. Минж энэ нь сайн анхаарахгүй бол бэлгэнд ѳгѳх цэцэг жижиг болох сул талтай юм гэж боджээ. Тэгээд тэр үүнд ямар нэгэн арга хэмжээ авахаар шийдэв.

Тѳрсѳн ѳдѳрт $m$ ѳдѳр үлдсэн байв. $i$-р цэцгийн ѳндѳр (цэцгүүдээ зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаарлагдсан гэж үзье) яг тэр үед $a_{i}$ байлаа. Үлдсэн $m$ ѳдѳр бүр минж дараалсан $w$ цэцгийг усална (ѳдѳрт нэг л удаа). Услагдсан цэцэг тэр ѳдрѳѳ нэг нэгжээр ѳснѳ. Минж эцэст нь хамгийн жижиг цэцгийн ѳндѳр аль болох их байхыг хүсч байна. Хамгийн жижиг цэцгийн ѳндѳр хамгийн ихдээ хэд байх вэ?

Оролт

Эхний мѳр зайгаар тусгаарлагдсан $n$, $m$, $w$ $(1 ≤ w ≤ n ≤ 10^{5}; 1 ≤ m ≤ 10^{5})$ бүхэл тоонуудыг агуулна. Хоёрдугаар мѳр зайгаар тусгаарлагдсан $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{9})$ бүхэл тоонуудыг агуулна.

Гаралт

Хамгийн жижиг цэцгийн боломжит хамгийн их ѳндрийг хэвлэ.

Орчуулсан: Sugardorj

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

Оролт
6 2 3
2 2 2 2 1 1
Гаралт
2
Оролт
2 5 1
5 8
Гаралт
9

Тэмдэглэл

Эхний жишээний хувьд минж сүүлийн 3 цэцгийг эхний ѳдѳр усална. Тэгэхэд цэцгүүдийн ѳндѳр [2, 2, 2, 3, 2, 2] болно. Дараагийн ѳдѳр яаж ч услаад бүгдийг нь гурваас багагүй ѳндѳртэй болгож чадахгүй. Иймд хариу нь 2 байна.

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