D. Маш нууц ажил

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

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

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

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

Хурандаа Зуевийн удирдлаган доорх маш нууц цэргийн бааз Хамгаалалтын яамнаас шалгалт хүлээж байна. Гэрээний дагуу маш нууц цэргийн бааз бүр ... хийх маш нууц цэргүүдтэй байх ёстой. Энэ цэргүүд нь маш нууц учир бид танд яг юу хийхийг нь хэлж чадахгүй нь. Асуудлын гол нь Зуевийн бааз уг маш нууц цэргүүдээ зарим шалтгааны улмаас алдчихсан.

Хурандаа асуудлыг түргэн цэгцлэхээр шийдсэн ба баазын түүнд итгэмжлэгдсэн $n$ цэргийг нэг эгнээнд жагсахыг тушаасан. Зуев зүүнээсээ $i$-р цэргийн чалчаа байдал нь $q_{i}$-тэй тэнцүү гэдгийг мэднэ. Зуев маш нууц цэргүүдийг шугамын хамгийн зүүн талын $k$ цэргийг ашиглан бүрдүүлэхийг хүсч байна иймээс Зуев тэдний нийт чалчаа байдал нь боломжит хамгийн бага (цэргүүд маш нууц байж чадахуйц) байхыг хүсч байна. Ингэхийн тулд тэр хоёр дараалласан цэрэг сонгох ба тэдгээрийг хооронд нь солино. Тэр $s$-с цөөн удаа үүнийг хийхийг зорьж байна. Ямар ч цэрэг уг солилцоонд хэдэн ч удаа орж болно. Асуудал ер бусын болж ирж байна иймд Зуев таны тусламжыг хүсч байна.

Хоёр дараалласан цэргийг солих үйлдлийг $s$-с ихгүй удаа гүйцэтгээд гаргаж авч болох жагсаалын эхний $k$ цэргийн нийт чалчаа байдал нь хамгийн багадаа хэд байхыг тооцоол.

Оролт

Оролтын эхний мөрөнд гурван эерэг бүхэл тоо $n$, $k$, $s$ ($1 ≤ k ≤ n ≤ 150$, $1 ≤ s ≤ 10^{9}$) байх ба харгалзан жагсаал дахь цэргүүдийн тоо, бүрдүүлэх шаардлагатай маш нууц цэргүүдийн хэмжээ ба дараалласан хоёр цэргийг хооронд нь сольж болох хамгийн их тоо байна.

Оролтын хоёр дахь мөрөнд $n$ бүхэл тоон утга $q_{i}$ ($1 ≤ q_{i} ≤ 1 000 000$) байх буюу жагссан цэргүүдийн чалчаа байдлын утга нь зүүнээс баруун тийш өгөгдөнө.

Гаралт

Маш нууц цэргүүдийн нийт чалчаа байдлын боломжит хамгийн бага утгыг илэрхийлэх нэг бүхэл тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 2 2
2 4 1
Гаралт
3
Оролт
5 4 2
10 1 6 2 5
Гаралт
18
Оролт
5 2 3
3 1 4 2 5
Гаралт
3

Тэмдэглэл

Эхний жишээн дээр Хурандаа хоёр ба гурав дахь цэргийг солих хэрэгтэй, түүнд үлдсэн солилцоонууд хэрэггүй. Гарч буй цэргүүдийн дараалал нь: ($2$, $1$, $4$) байна. Маш нууц цэргүүдийн нийт чалчаа байдлын боломжит хамгийн бага утга нь $3$. Хоёр дахь жишээн дээр Хурандаа солилцоонуудыг дараах дарааллаар хийнэ:

  1. $(10, 1, 6$ -- $2$, 5)
  2. $(10, 1, 2, 6$ -- $5$)

Ингээд үүсэх цэргүүдийн дараалал нь (10, 1, 2, 5, 6).

Нийт чалчаа байдлын боломжит хамгийн бага утга нь $18$.

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