D. Дэлгүүр

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

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

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

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

Вася бараг хүн болгоны мэддэг нэгэн төрлийн MMORPG тоглоом тоглодог. Түүний тоглоомын баатар $k$ чадвартай ба одоогийн байдлаар $i$-р чадвар нь $a_{i}$-тэй тэнцүү байгаа. Мөн энэ тоглоомонд баатарын бүх чадваруудын үржвэрээр нь оролцогчдыг буурах дарааллаар үнэлсэн нэгдсэн үнэлгээний хүснэгт байдаг.

Вася тоглоомын дэлгүүрийн сайтаар дамжуулан өөрийн баатраа сайжруулахаар шийджээ. Энэ дэлгүүр баатрынхаа чадварыг сайжруулах $n$ боломжит арга замуудыг санал болгодог. Эдгээр арга бүр нь дараах гурван төрлийн аль нэгэнд хамаарагддаг:

  1. $i$-р чадварыг $b$ болгоно.
  2. $i$-р чадвар дээр $b$-г нэмнэ.
  3. $i$-р чадварыг $b$-р үржүүлнэ.

Гэхдээ анхаарах хоёр зүйл бий, нэгдүгээрт сайжруулалт бүрийг нэг удаа л ашиглаж болно, хоёрдугаарт Васягийн картанд нийт $n$ сайжруулалтаас хамгийн ихдээ $m$ ширхэгийг худалдан авах мөнгө байгаа. Тоглоомны хамгийн өндөр үнэлгээнд хүрэхэд Васяд туслаарай. Үүний тулд тэр ямар сайжруулалтуудыг худалдан авахыг Васяд хэлнэ үү, мөн тэр эдгээр сайжруулалтуудыг аль болох өндөр үнэлгээнд хүрэхийн тулд ашиглах ёстой. Хэд хэдэн арга байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

Оролт

Эхний мөрөнд $k, n, m$ ($1 ≤ k ≤ 10^{5}$, $0 ≤ m ≤ n ≤ 10^{5}$) гурван бүхэл тоо байна. Эдгээр нь чадваруудын тоо, худалдаалж байгаа сайжруулалтын тоо, мөн тэдгээрээс Васягийн худалдан авч чадах сайжруулалтын тоо юм.

Хоёр дахь мөрөнд чадваруудын анхны утгууд болох зайгаар тусгаарлагдсан $k$ ширхэг $a_{i}$ ($1 ≤ a_{i} ≤ 10^{6}$) тоонууд байна.

Дараагийн $n$ мөрүүдэд зайгаар тусгаарлагдсан $t_{j}, i_{j}, b_{j}$ ($1 ≤ t_{j} ≤ 3, 1 ≤ i_{j} ≤ k, 1 ≤ b_{j} ≤ 10^{6}$) гурван тоо байна. Эдгээр нь $j$-р сайжруулалтын төрөл (утга олгох бол $1$, нэмэх бол $2$, үржүүлэх бол $3$), үүнийг хэрэглэж болох чадвар, мөн энэ сайжруулалтын параметр болох $b$ утга юм.

Гаралт

Эхний мөрөнд таны хэрэглэх ёстой сайжруулалтуудын тоо болох $l$ ($0 ≤ l ≤ m$) тоо байна.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан, ялгаатай $l$ ширхэг $v_{i}$ ($1 ≤ v_{i} ≤ n$) тоонууд байна. Сайжруулалтуудын дугаарлалт нь тэдгээрийг хэрэглэх дарааллаар байх ёстой. Сайжруулалтуудыг оролтын дарааллаар $1$-ээс эхлэн дугаарласан байна.

Орчуулсан: Даариймаа

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

Оролт
2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2
Гаралт
3
2 3 4
Сэтгэгдлүүдийг ачааллаж байна...