C. Худалдааны бизнес

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

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

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

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

Шинэ загварын ионжуулсан хурдасгуур авахын тулд Квэрти худалдаа хийхээр шийджээ. Тэрээр нэг гаригаас хэсэг бараа худалдан авч өөр нэг гариг дээр зарахаар болжээ (эсвэл бараа худалдаж авахгүй байж болно). Энэ ажиллагааг ганц л удаа хэрэгжүүлнэ. Ажиллагаагаа хэрэгжүүлэхийн тулд банкнаас мөнгө зээлж ажиллагаа дууссаны дараа мөнгөө буцааж өгнө (банкнаас зээлсэн мөнгөний хүүг тооцохгүй). Үүнээс гадна Квэрти энэ ажиллагаагаар аль болох их хэмжээний ашиг олохыг хүсэж байгаа.

Системд нийт $n$ ширхэг гариг байна. Гариг болгонд Квэрти $m$ төрлийн бараа худалдан авч эсвэл зарж болно (хоол, эм, зэвсэг, алкохол гэх мэт). Квэрти $i$ дэхь гариг бүрийн $j$ дэхь бараа болгоны хувьд дараах зүйлсийг мэдэж байгаа:

  • $a_{ij}$ - барааны худалдаж авах үнэ
  • $b_{ij}$ - барааны зарах үнэ
  • $c_{ij}$ - барааны байгаа тоо

$i$ гариг дээрх $j$ төрлийн бараанаас $c_{ij}$-ээс олон ширхэгийг худалдан худалдан авах боломжгүй. Харин аль ч төрлийн бараанаас хэдэн ч ширхэгийг зарж болно.

Квэртигийн онгоцонд нийт $k$ ширхэг бараанаас илүү бараа багтахгүй бол Квэртигийн олж болох хамгийн их ашгийг ол.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд болох $n$, $m$, $k$ ($2 ≤ n ≤ 10$, $1 ≤ m, k ≤ 100$) өгөгдөнө. Эдгээр нь нийт гаригийн тоо, барааны төрөл болон Квэртигийн онгоцны багтаамж юм.

Дараагийн $n$ ширхэг хайрцганд гариг болгоныг тодорхойлсон өгөгдлүүд өгөгдөнө.

$i$ дэхь хайрцагны эхний мөрөнд гаригийн нэрийг $1$-ээс $10$-ийн хооронд хэмжээтэй тэмдэгт мөрөөр өгнө. Нэрний эхний үсэг том үлдсэн нь жижиг үсэг байх юм. $i$ дэхь хайрцагны дараагийн $m$ ширхэг мөрний $j$ дэхь мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $a_{ij}$, $b_{ij}$, $c_{ij}$ ($1 ≤ b_{ij} < a_{ij} ≤ 1000$, $0 ≤ c_{ij} ≤ 100$) өгөгдөнө. Эдгээр тоонууд нь $i$ дэхь гаригийн $j$ дэхь барааны үзүүлэлтүүдийг заана.

Бүх гаригуудын нэр өөр хоорондоо ялгаатай.

Гаралт

Квэртигийн олж чадах хамгийн их ашиг болох нэг тоог хэвлэ.

Орчуулсан: Энхлут

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

Оролт
3 3 10
Venus
6 5 3
7 6 5
8 6 10
Earth
10 9 0
8 6 4
10 9 3
Mars
4 3 0
8 4 12
7 2 5
Гаралт
16

Тэмдэглэл

Эхний тестэнд Venus гариг дээр очин $74$ нэгж мөнгө зээлж аван $1$ дэхь төрлийн бараанаас $3$-ыг, $3$ дахь төрлийн бараанаас $7$-г худалдан авна ($3 \cdot 6 + 7 \cdot 8 = 74$). Дараа нь Earth гариг дээр очин бүх бараагаа зарна. Ингэснээр тэрээр нийт $3 \cdot 9 + 7 \cdot 9 = 90$ нэгж мөнгө олж чадах бөгөөд үүний $74$-ийг нь банкинд буцааж төлнө. Ингээд нийт $16$ нэгж мөнгөний ашиг олж чадна. Энэ нь олж болох хамгийн их ашиг юм.

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