B. Лемингүүд

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

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

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

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

Таны мэдэж байгаачлан Лемингүүд (сохор номинтой төстэй нэгэн төрлийн амьтан) нь үсрэх дуртай байдаг. Дараагийн $n$ ширхэг Лемингүүдийн бүлэг үсрэлт нь $k$ ширхэг тохиромжтой ирмэгтэй нэгэн өндөр хадны дэргэд болох юм. Эхний ирмэг нь $h$ метрийн өндөрт байрласан бөгөөд 2-дахь ирмэг нь $2h$ метрийн өндөрт гэх мэтчилэн байрлалтай байх юм ($i$-дахь ирмэг нь $i*h$ метрийн өндөрт байрлалтай байна). Лемингүүд нь нар жаргах үед үсрэх бөгөөд одоо тэдэнд нэг их цаг үлдээгүй байв.

Леминг болгон нь өөрийн авиралтын хурд болох $v_{i}$ метр/минут болон өөрийн жин $m_{i}$-аар тодорхойлогдоно. Энэ нь $i$-дахь Леминг $j$-дэх ирмэг уруу минутад авирч чадна гэсэн үг юм.

Сайхан харагдаж үсрэхийн тулд хүнд Лемингүүд нь өндөр ирмэгээс үсрэх ёстой байв: хэрэв $m_{i}$ жинтэй нэгэн Леминг $i$ ирмэгээс үсрэх ба $m_{j}$ жинтэй нэгэн Леминг $j$ (for $i < j$) ирмэгээс үсрэх бол $m_{i} ≤ m_{j}$ гэсэн тэнцэтгэл биш нь заавал биелэх ёстой байна.

Нийт $n$ ширхэг Леминг болон зөвхөн $k$ ($k ≤ n$) ширхэг ирмэг байгаа учраас $k$ ширхэг үсрэлтэд оролцох ёстой Лемингүүд нь сонгогдох ёстой болох юм. Сонгогдсон Лемингүүд нь $1$-ээс $k$ хүртэлх ирмэгүүд дээр нэг ирмэг дээр нэг Леминг байхаар байрлах ёстой ажээ. Түүнчлэн Лемингүүд нь жингийн үл буурах дарааллаар эрэмбэлэгдсэн байх бөгөөд уг дарааллаараа багаасаа эхлэн ирмэгүүд дээр байрлах ба ирмэгүүдийн өндөр нь өсөх дарааллаар Лемингүүдэд харгалзсан байх юм. Мөн Леминг болгон нь өөрийн ирмэг дээрээ хүрч очих хангалттай цагтай байх ёстой бөгөөд өөрөөр хэлбэл түүний авирах хугацаа нь $t$ минутаас хэтрэхгүй байх ёстой. Лемингүүд нь хугацааны нэг ижил мөчид бүх ирмэгүүд дээрээ авирах бөгөөд тэд өөр хоорондоо ямар нэгэн саад учруулахгүй гэж үзэх юм.

Тэгвэл $t$-ын утга нь хамгийн бага байхаар Лемингүүдийн үсрэлтүүдийг зохицуулах арга олж өгнө үү.

Оролт

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

2-дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоонууд $m_{1}, m_{2}, ..., m_{n}$ ($1 ≤ m_{i} ≤ 10^{9}$)-ууд өгөгдөх ба энд $m_{i}$ нь $i$-дахь Лемингийн жинг илэрхийлнэ.

3-дахь мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоонууд $v_{1}, v_{2}, ..., v_{n}$ ($1 ≤ v_{i} ≤ 10^{9}$)-ууд өгөгдөх ба энд $v_{i}$ нь $i$-дахь Лемингийн хурдыг илэрхийлнэ.

Гаралт

Хэрэв үсрэлт нь оновчтой байдлаар зохион байгуулагдах бол харгалзан $h, 2h, ..., kh$ өндөртэй ирмэгүүд уруу авирах Лемингүүдийн дугаар болох $1$-ээс $n$ хүртэлх $k$ ширхэг ялгаатай тоонуудыг хэвлэнэ үү. Хэрэв Лемингүүдийг сонгох олон тооны арга байвал тэдгээрийн алийг нь ч сонгосон болно.

Орчуулсан: Баатархүү

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

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

Тэмдэглэл

Эхний жишээг авч үзье. 5-дахь Леминг (10 хурдтай) 2 өндөртэй ирмэг дээр минутын дараа очно; 2-дахь Леминг (2 хурдтай) 4 өндөртэй ирмэг дээр 2 минутын дараа очно; 4-дэх Леминг (2 хурдтай) 6 өндөртэй ирмэг дээр 3 минутын дараа очно. Иймд бүх Лемингүүд нь өөрийн очих ёстой байрлал дээр 3 минутын дотор очиж чадна.

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