A. Хулгай

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

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

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

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

Жое шѳнийн цагаар улсын тѳв банкны сэйфэнд нэвтрэв. Сэйф нэг эгнээнд байрласан $n$ нүднээс бүрдэх ба, нүд бүр хэдэн ширхэг алмаз агуулна. Энэхүү бодлоготой илүү амар ажиллахын тулд эдгээр нүднүүдээ зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаарлагдсан гэе.

Харамсалтай нь Жое хамгаалалтын системийг унтрааж чадахгүй. Гэхдээ сайн тал нь тэр үүнийг хэрхэн ажилладгийг мэддэг бажээ.

Минут бүрт хамгаалалатын систэм зэрэгцээ хоёр нүд бүрийн нийлбэрийг тооцоолдог (хоорондох зѳрүү нь нэгээс хэтэрдэггүй нүднүүдийн). Үүний үр дүнд гарсан $n-1$ ширхэг нийлбэрийг шалгана. Хэрэв эдгээр нийлбэрээс ядаж нэг нь ѳмнѳх шалгалтын хргалзах нийлбэрээсээ ялгаатай байвал хамгаалалтын систэм дохио ѳгч бүхнийг түгжнэ.

Жое хамгаалалтын систэмийн шалгалтуудын хооронд алмазнуудыг нэг нүднээс нѳгѳѳ рүү шилжүүлнэ. Тэрээр хоёр шалгалтын хооронд $m$-ээс ихгүй үйлдэл хийж чаддаг. Дараах гурван үйлдлийн нэгийг нэг үйлдлээр хийж болно: дурын нүднээс нэг алмазыг дуртай нүд рүүгээ шилжүүлэх, дурын нүднээс нэг алмазыг Жоеийн түрийвч рүү шилжүүлэх, Жоеийн түрийвчнээс нэг алмазыг дурын нүд рүү шилжүүлэх. Анх Жоеийн түрийвч хоосон байсан бѳгѳѳд үүнд ямар ч тооны алмазыг багтаах боломжтой. Жоеийг ирэхээс ѳмнѳ хамгаалалтын систэмийн ядаж нэг шалгалт явагдсан гэж үзнэ.

Банкны ажилчдыг ѳглѳѳ ирэхэд Жое банкийг орхин явсан байх ёстой. Ѳглѳѳ болтол Жоед ердѳѳ $k$ минут үлдсэн ба эдгээр $k$ минут бүрт тэр $m$-ээс ихгүй үйлдэл гүйцэтгэж чадна. Эцэст нь түүний түрийвчинд үлдсэн зүйлийг түүний хулгайн олз болно гэж үзнэ.

Жоеийн авч чадах хамгийн их хэмжээний алмазны тоог ол. Хамгаалалтын систэмийн дохиог дугаргах ёсгүй (бүр гарсны дараа хүртэл) болон Жое ѳглѳѳ болохоос ѳмнѳ явах хэрэгтэй гэдгийг битгий мартаарай.

Оролт

Эхний мѳр $n$, $m$, $k$ ($1 ≤ n ≤ 10^4$, $1 ≤ m, k ≤ 10^9$) бүхэл тоонуудыг агуулна. Дараагийн мѳр $n$ ширхэг тоог агуулна. $i$-дэх тоо нь $i$-р нүдэн дэх алмазны тоо болох $0$-ээс $10^5$ хүртэлх бүхэл тоо байна.

Гаралт

Жоеийн хулгайлж чадах алмазны хамгийн их тоо болох ганц тоог хэвлэ.

Орчуулсан: Sugardorj

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

Оролт
2 3 1
2 3
Гаралт
0
Оролт
3 2 2
4 1 3
Гаралт
2

Тэмдэглэл

In the second sample Joe can act like this:

The diamonds' initial positions are $4$ $1$ $3$.

During the first period of time Joe moves a diamond from the $1$-th cell to the $2$-th one and a diamond from the $3$-th cell to his pocket.

By the end of the first period the diamonds' positions are $3$ $2$ $2$. The check finds no difference and the security system doesn't go off.

During the second period Joe moves a diamond from the $3$-rd cell to the $2$-nd one and puts a diamond from the $1$-st cell to his pocket.

By the end of the second period the diamonds' positions are $2$ $3$ $1$. The check finds no difference again and the security system doesn't go off.

Now Joe leaves with $2$ diamonds in his pocket.

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