B. Зальт Гена

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

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

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

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

Гена хүү "Оросын Кодын Цом"-ын эцсийн даваанд шалгарах эсвэл ядаж л богино цамцаар шагнуулахыг ихэд хүсч байв. Гэхдээ бодлогууд хэт хүнд байсан тул тэрээр $n$ найзтайгаа түүнд бодлого бодож өгөх тохиролцоо хийж гэнэ.

Тэмцээнд $m$ бодлого өгөгджээ. Гена найз бүрийнхээ бодож чадах бодлогуудыг мэдэж байгаа. Найзууд нь түүнд хариу шаардлага тавив: $i$ дэх найз нь түүнээс чадах бүх бодлогоо бодсоны хариуд $x_{i}$ рубль хүсчээ. Мөн Генагийн компьютер дор хаяж $k_{i}$ дэлгэцэнд холбогдсон үед л тусална гэж хэлэв. Дэлгэц бүр $b$ рублийн үнэтэй.

Гена мөнгөнд их гамтай тул бүх бодлогоо бодохдоо хамгийн бага мөнгө зарцуулахыг хүсчээ. Гена хэрхэн хамгийн бага зардал гаргахыг хэлж өгч тусална уу. Анх Генагийн компьютер нэг ч дэлгэцтэй холбогдоогүй байгаа.

Оролт

Эхний мөрөнд Генагийн найзуудын тоо, бодлогуудын тоо болон нэг дэлгэцийн үнийг илэрхийлэх $n$, $m$, $b$ $(1 ≤ n ≤ 100$; $1 ≤ m ≤ 20$; $1 ≤ b ≤ 10^{9})$ гэсэн бүхэл тоонууд өгөгдөнө.

Дараагийн $2n$ мөрөнд найзуудын мэдээлэл байна: $2i$ ба $(2i + 1)$ дугаарын мөрөнд $i$ дэх найзын мэдээлэл байна. $2i$ дугаарын мөрөнд $x_{i}$, $k_{i}$ ба $m_{i}$ ($1 ≤ x_{i} ≤ 10^{9}$; $1 ≤ k_{i} ≤ 10^{9}$; $1 ≤ m_{i} ≤ m$) гэсэн гурван бүхэл тоо байх ба харгалзан хүсэж байгаа мөнгөний хэмжээ, хүссэн дэлгэцийн тоо болон түүний бодож чадах бодлогын тоог илэрхийлнэ. $(2i + 1)$ дугаарын мөрөнд $m_{i}$ ширхэг ялгаатай тоо байх ба эдгээр нь $i$ дэх найзын бодож чадах бодлогуудын дугаарыг илэрхийлнэ. Бодлогууд $1$-ээс $m$ хүртэл дугаарлагдсан.

Гаралт

Бүх бодлогыг бодохын тулд Гена хамгийн багадаа хэчнээн рубль зарах ёстойг хэвлэ. Хэрэв бүх бодлогыг бодох боломжгүй бол "-1" гэж хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
2 2 1
100 1 1
2
100 2 1
1
Гаралт
202
Оролт
3 2 5
100 1 1
1
100 1 1
2
200 1 2
1 2
Гаралт
205
Оролт
1 2 1
1 1 1
1
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...