E. Биологич

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

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

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

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

СмоллАр бол биологич. Түүний хамгийн сүүлийн судалгааны ажлын сэдэв нь "Хэрхэн нохдын хүйсийг солих вэ?" байсан. Өөрөөр хэлбэл тэр эм нохдыг эр болгож, эр нохдыг эм болгож чадна.

Тэр одоо энэ аргаа батлах гэж байна. Одоо СмоллАрд $n$ нохой байгаа ба нохой бүрийг өөрчлөх нь ялгаатай өртөгтэй байж болно. Нохойнуудыг 1-с $n$ хүртэл дугаарласан. $i$ нохойны хувьд өөрчлөх өртөг нь $v_{i}$ RMB. Энэ аргад зөвхөн нэг өдөр л хүчинтэй байдаг нэгэн төрлийн эм хэрэглэдэг. Туршилт нэг өдөрт хийгдэх ба нохой бүр хамгийн ихдээ нэг л удаа өөрчлөгдөх боломжтой.

Энэ туршилт нийгмийн бүхий л хүрээнд маш их анхаарал татсан. Энэ туршилтыг сэрдэж байгаа $n$ баян хүмүүс байгаа. Тэд бүгд СмоллАртай хүчээр бооцоо тавихыг хүссэн. Хэрвээ СмоллАр амжилттай хийвэл $i$-р хүн СмоллАрд $w_{i}$ RMB төлнө. Гэхдээ тэд СмоллАрийг амжилттай хийсэн эсэхийг шалгахдаа тусгай арга ашиглах нь хачирхалтай. $i$-р хүний хувьд тэр хүн урьдаас тодорхой $k_{i}$ ноход болон нэг хүйс сонгоно. Тэр зөвхөн аль нэг өдөр сонгосон $k_{i}$ нохдын хүйс тодорхойлсон хүйстэй байвал л СмоллАрийг туршилтаа амжилттай гүйцэтгэсэн гэж үзнэ. Бусад тохиолдолд тэр СмоллАрийг бүтэлгүйтсэн гэж бодно.

Хэрвээ СмоллАр өөрийн найз биш зарим баян хүмүүсийн шаардлагыг хангаагүй тохиолдолд тэдгээр хүмүүст мөнгө төлөх шаардлагагүй, харин өөрийн найз баян хүний шаардлагыг хангаагүй тохиолдолд түүнээс уучлалт хүсч $g$ RMB төлөх ёстой.

Ингээд СмоллАр энэ туршилтаас боломжит хамгийн их мөнгийг олж авч чадна гэдэгтээ итгэлтэй байна. СмоллАрд түүний олж чадах хамгийн их мөнгийг тооцоолж өгнө үү. Мэдээж тэр ямар ч мөнгө олохгүй харин алдаж магадгүй. Энэ тохиолдолд түүний алдах ёстой мөнгөний хамгийн бага хэмжээг гаргана уу.

Оролт

Эхний мөрөнд гурван бүхэл тоо $n$, $m$, $g$ $(1 ≤ n ≤ 10^{4}, 0 ≤ m ≤ 2000, 0 ≤ g ≤ 10^{4})$ байна. Хоёр дахь мөрөнд $n$ бүхэл тоо байх ба тус бүр нь 0 эсвэл 1 байх ба 0 нь нохой эм хүйстэйг илэрхийлэх бол 1 нь нохой эр хүйстэйг илэрхийлнэ. Гурав дахь мөрөнд $n$ бүхэл тоо $v_{1}, v_{2}, ..., v_{n}$ $(0 ≤ v_{i} ≤ 10^{4})$ байна.

Дараагийн $m$ мөр тус бүрт уг баян хүнийг тодорхойлно. $i$-р мөрөнд эхлээд $i$-р хүний хүйсийг илэрхийлсэн нэг тоо (0 эсвэл 1) байна , дараагийн хоёр бүхэл тоо нь $w_{i}$ ба $k_{i}$ $(0 ≤ w_{i} ≤ 10^{4}, 1 ≤ k_{i} ≤ 10)$ байх ба дараагийн $k_{i}$ ялгаатай бүхэл тоо нь энэ хүний сонгосон нохойнуудын дугаар (дугаар бүр 1-с $n$ хооронд байна) байна. Энэ мөрийн хамгийн сүүлийн тоо нь $i$-р хүн нь СмоллАрийн сайн найз мөн эсэхийг тодорхойлно (0 байвал биш, 1 байвал мөн).

Гаралт

СмоллАрийн олж чадах мөнгөний хамгийн их хэмжээг илэрхийлэх нэг бүхэл тоог хэвлэ. Хэрвээ СмоллАр мөнгө алдахаар бол энэ тоо сөрөг байна.

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

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

Оролт
5 5 9
0 1 1 1 0
1 8 6 2 3
0 7 3 3 2 1 1
1 8 1 5 1
1 0 3 2 1 4 1
0 8 3 4 2 1 0
1 7 2 4 1 1
Гаралт
2
Оролт
5 5 8
1 0 1 1 1
6 5 4 2 8
0 6 3 2 3 4 0
0 8 3 3 2 4 0
0 0 3 3 4 1 1
0 10 3 4 3 1 1
0 4 3 3 4 1 1
Гаралт
16
Сэтгэгдлүүдийг ачааллаж байна...