E. Эрдэнэсийг гарга

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

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

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

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

Рэйнбөв нэг мөрөнд байрласан 1-c $h$ хүртэл дугаарлагдсан $h$ үүр байгуулсан. Энд эрдэнэс агуулсан $n$ үүр байгаа. Бид эдгээр $n$ үүр бүрийг "Эрдэнэстэй үүр" гэж нэрлэнэ. $i$-р "Эрдэнэстэй үүр" бол $a_{i}$ дугаартай үүр ба эрдэнэсийн үнэ нь $c_{i}$ доллар байна.

Фреда эхний үүрэнд очсон. Тэр одоо урагшаа $k$ үүр явж чадах ба эсвэл эхний үүррүү буцаж болно. Энэ нь Фреда эхний, ($k + 1$)-р, ($2*k + 1$)-р, ($3*k + 1$) гээд үргэлжлэн явах боломжтой гэсэн үг.

Рэйнбөв Фредад $m$ үйлдэл өгсөн. Үйлдэл бүр дараах гурван төрлийн нэг байна:

  1. Өөр $x$ арга нэмэх: тэр дурын мөчид урагшаа $x$ үүр явж чаддаг болох. Жишээлбэл анх тэр зөвхөн нэг $k$ аргатай байна. Хэрвээ хугацааны тухайн нэг мөчид тэрэнд $a_{1}, a_{2}, ..., a_{r}$ аргууд байвал Фреда хэлбэртэй дугаар бүхий бүх үүрнүүдэд очиж болох ба энд $v_{i}$ нь эерэг бүхэл тоо байна.
  2. $x$-р "Эрдэнэстэй үүр"-ний эрдэнэсийн үнийг $y$ доллараар багасга. Өөрөөр хэлбэл $c_{x} = c_{x} - y$ болго.
  3. Фредагийн хүрч чадах үүрнүүдийн дундаас хамгийн үнэтэй эрдэнэсийн үнийг олох. Хэрвээ Фреда ямар ч эрдэнэстэй үүрэнд хүрэх боломжгүй бол хамгийн үнэтэй эрдэнэс 0-тэй тэнцүү ба юу ч хийхгүй. Бусад тохиолдолд хамгийн үнэтэй эрдэнэсийг авч хаяна. Хэрвээ хамгийн үнэтэй эрдэнэстэй хэд хэдэн "Эрдэнэстэй үүр" байвал хамгийн бага дугаартай "Эрдэнэстэй үүр"-ийг нь хая (хамгийн бага дугаартай үүр биш). Үүний дараа эрдэнэстэй үүрүүдийн нийт тоо нэгээр багасна.

Фреда таныг асуулга бүрт хариулдаг програм бичихийг хүсч байна.

Оролт

Оролтын эхний мөрөнд дөрвөн бүхэл тоо $h (1 ≤ h ≤ 10^{18}), n, m (1 ≤ n, m ≤ 10^{5})$ ба $k (1 ≤ k ≤ 10^{4})$ байна.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоо $a_{i} (1 ≤ a_{i} ≤ h), c_{i} (1 ≤ c_{i} ≤ 10^{9})$ байна. Энэ нь $i$-р "Эрдэнэстэй үүр" нь $a_{i}$-р үүр гэдгийг илэрхийлэх ба энэ үүрэнд байгаа эрдэнэс $c_{i}$ долларын үнэтэй гэдгийг илэрхийлнэ. Бүх $a_{i}$ ялгаатай байна.

Дараагийн $m$ мөр бүр дараах гурван форматын аль нэгнийх нь дагуу байна:

  • "1 $x$" буюу 1 төрлийн үйлдэл, $1 ≤ x ≤ h$;
  • "2 $x$ $y$" буюу 2 төрлийн үйлдэл, $1 ≤ x ≤ n, 0 ≤ y < c_{x}$;
  • "3" буюу 3 төрлийн үйлдэл.

1 төрлийн үйлдэл хамгийн ихдээ 20 байна. Дурын мөчид үүр бүрт байгаа эрдэнэсийн үнэ эерэг байна. Бүх үйлдэл зөв байна (ямар ч үйлдэл хаягдсан эрдэнэсийн үнийг багасгахгүй).

C++ хэлэнд 64 битийн бүхэл тонуудыг унших болон бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. $cin$, $cout$ урсгалууд болон $\%I64d$ тодорхойлогчийг ашиглаарай.

Гаралт

3 төрлийн үйлдэл бүрийн хувьд "Эрдэнэстэй үүр"-нүүдийн дундаас Фредагийн хүрч чадах хамгийн үнэтэй эрдэнэсийн үнийг (доллараар) тодорхойлох нэг бүхэл тоог хэвлэ. Хэрвээ ийм эрдэнэс байхгүй бол 0-г хэвлэ.

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

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

Оролт
10 3 5 2
5 50
7 60
8 100
2 2 5
3
1 3
3
3
Гаралт
55
100
50

Тэмдэглэл

Жишээн дээр нийт 10 үүр байгаа ба тэдний 3 нь "Эрдэнэстэй үүр". Эхний "Эрдэнэстэй үүр" нь 5 дугаартай үүр ба эрдэнэс нь 50 доллар. Хоёр дахь "Эрдэнэстэй үүр" нь 7 дугаартай үүр ба эрдэнэс нь 60 доллар. Гурав дахь "Эрдэнэстэй үүр" нь 8 дугаартай үүр ба эрдэнэс нь 100 доллар.

Эхлээд Фреда зөвхөн 1, 3, 5, 7 ба 9 дугаартай үүрэнд очиж чадна. Эхний үйлдэлд бид 2 дахь "Эрдэнэстэй үүр"-ний үнийг 60-с 55 болгож буулгана. Ингээд түүний хүрч чадах "Эрдэнэстэй үүрнүүдээс" хамгийн үнэтэй нь max(50, 55) = 55 байна. Гурав дахь үйлдлийн дараа тэр алхам бүртээ 3 үүр урагш явж чаддаг болох ба 1, 3, 4, 5, 6, 7, 8, 9, 10 үүрүүдрүү очиж чадна. Ингээд хамгийн үнэтэй эрдэнэс нь 100 доллар байна.

Тэр 55 болон 100 долларын эрдэнэсүүдийг хаясан учраас сүүлийн хариулт 50 байна.

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