Леша домогт тоглоом Хакнет-ийн саяхан гарсан загварыг тоглодог. Тус загварт баатруудын ур чадварыг танилцуулжээ. Одоо баатар болгон яг $n$ ширхэг ур чадвартай байх юм. Ур чадвар болгон нь уг чадварын одоо байгаа төвшин болох сөрөг биш бүхэл тоо $a_{i}$-аар илэрхийлэгдэнэ. Бүх ур чадварууд нь хамгийн ихдээ ижилхэн $A$ төвшинтэй байж болно.

Ур чадварын дагуу бүх тоглогчдын дэлхийн чансаа мөн нэмэгджээ. Тоглогчид нь ХҮЧ-ын дагуу тус чансаанд эрэмбэлэгдэнэ. Тоглогчийн ХҮЧ гэдэг нь дараах утгуудын нийлбэр байна:

• Тоглогчийн баатрын төгс болгосон чадварын тоог (ө.х., $a_{i} = A$ байх чадварын тоо) $c_{f}$ коэффициентээр үржүүлнэ.
• Бүх чадвар дундах хамгийн бага төвшинтэй ($min a_{i}$) чадварыг $c_{m}$ коэффициентээр үржүүлнэ.

Одоо Леша-д $m$ ширхэг Хакнетиан валютын нэгж байгаа ба тэрээр эдгээрийг үрэх сонирхолтой байгаа юм. Валютын нэгж бүр нь ямар ч чадварын одоогийн төвшинг (хэрэв энэ нь хараахан $A$ болоогүй бол) $1$-ээр ихэсгэж чадна. Түүний баатар нь боломжит хамгийн их ХҮЧ-ын утгатай байхаар мөнгийг нь үрж өгнө үү.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 5 бүхэл тоо $n$, $A$, $c_{f}$, $c_{m}$ болон $m$ ($1 ≤ n ≤ 100 000$, $1 ≤ A ≤ 10^{9}$, $0 ≤ c_{f}, c_{m} ≤ 1000$, $0 ≤ m ≤ 10^{15}$) өгөгдөнө.

2-дахь мөрөнд чадваруудын одоогийн төвшин болох зайгаар тусгаарлагдсан яг $n$ ширхэг бүхэл тоо $a_{i}$ ($0 ≤ a_{i} ≤ A$) өгөгдөнө.

Гаралт

Эхний мөрөнд $m$-ээс ихгүй валютын нэгж ашиглан үүсгэж болох баатрын ХҮЧ-ын хамгийн их утгыг хэвлэнэ.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a'_{i}$ ($a_{i} ≤ a'_{i} ≤ A$)-г хэвлэнэ. Эдгээр нь $m$-ээс ихгүй валютын нэгж ашиглан ХҮЧ нь хамгийн их байхаар үүсгэсэн баатрын шинэчлэгдсэн чадваруудын төвшинүүд юм. Тоонууд нь зайгаар тусгаарлагдсан байна.

Эхний жишээнд оновчтой арга нь 2-дахь чадварыг хамгийн их төвшинд хүргэх ба бусад 2 чадварыг нь $1$-ээр ихэсгэх юм.

2-дахь жишээнд Леша бүх чадварыг хамгийн их төвшинд хүргэх юм.