D. Төхөөрөмжүүд доллараар болон паундаар

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

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

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

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

Нура $k$ төхөөрөмж худалдаж авахыг хүсч байна. Үүнд зориулж Нурад зөвхөн $n$ бурле байгаа. Тэр төхөөрөмж бүрийг доллар эсвэл паундаар худалдаж авч болно. Иймд төхөөрөмж бүр зөвхөн ямар нэг төрлийн валютаар л зарагдана. Валютын төрөл болон тухайн валютаар илэрхийлэгдэх үнэ өөрчлөгдөхгүй.

Нура $n$ өдрийн турш төхөөрөмжүүдээ авч болно. Өдөр бүрийн хувьд та доллар болон паундын арилжах харьцааг мэдэх ба мөн бурле-г доллар болон паундруу хөрвүүлэх үнийг мэднэ.

Өдөр бүр ($1$-с $n$ хүртэл) Нура тухайн арилжах харьцаагаар хэд хэдэн төхөөрөмж авч болно. Өдөр бүр Нура хүссэн төхөөрөмжөө авч болох боловч $n$ өдрийн турш төхөөрөмж бүрээс нэгийг л авч болно.

Нурад $k$ төхөөрөмжтэй болох хамгийн бага өдрийн индексийг олоход туслана уу. Нура зөвхөн тухайн өдрийн ханшаар доллар болон паундруу хөрвөж чадах бурле-г л ашиглана. Нура доллар болон паунд худалдаж авч чадахгүй ба зөвхөн бурле л хадгална. Төхөөрөмжүүд оролтонд өгөгдсөн дарааллаараа $1$-с $m$ хүртэл дугаарлагдана.

Оролт

Эхний мөрөнд дөрвөн бүхэл тоон утга $n, m, k, s$ ($1 ≤ n ≤ 2*10^{5}, 1 ≤ k ≤ m ≤ 2*10^{5}, 1 ≤ s ≤ 10^{9}$) байх ба өдрүүдийн тоо, төхөөрөмжүүдийн нийт болон шаардлагатай тоо ба Нурад байгаа бурлегийн тоо.

Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{i}$ ($1 ≤ a_{i} ≤ 10^{6}$) байх ба $i$-р өдөр дахь нэг доллартай тэнцэх бурле-н үнэ.

Гурав дахь мөрөнд $n$ бүхэл тоон утга $b_{i}$ ($1 ≤ b_{i} ≤ 10^{6}$) байх ба $i$-р өдөр дахь нэг паундтай тэнцэх бурле-н үнэ.

Дараагийн $m$ мөр бүрт хоёр бүхэл тоон утга $t_{i}, c_{i}$ ($1 ≤ t_{i} ≤ 2, 1 ≤ c_{i} ≤ 10^{6}$) байх ба төхөөрөмжийн төрөл ба үнэ байна. Эхний төрлийн төхөөрөмжүүдийн хувьд үнэ нь доллараар байна. Хоёр дахь төрлийн төхөөрөмжүүдийн хувьд үнэ нь паундаар байна.

Гаралт

Хэрвээ Нура $k$ төхөөрөмж худалдаж авч чадахгүй бол $-1$-г нэг мөрөнд хэвлэ.

Бусад тохиолдолд эхний мөрөнд бүхэл тоон утга $d$ байх ба Нура $k$ төхөөрөмжтэй болох хамгийн бага өдрийн индекс байна. Дараагийн $k$ мөр бүрт хоёр бүхэл тоон утга $q_{i}, d_{i}$ хэвлэх ба төхөөрөмжийн дугаар ба төхөөрөмжийг авах ёстой өдрийн дугаар байна. Бүх $q_{i}$ утга ялгаатай боловч $d_{i}$ утга ижил байж болно (Нура нэг өдөрт хэд хэдэн төхөөрөмж худалдан авч болно). Өдрүүд $1$-c $n$ хүртэл дугаарлагдана.

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

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

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

Оролт
5 4 2 2
1 2 3 2 1
3 2 1 2 3
1 1
2 1
1 2
2 2
Гаралт
3
1 1
2 3
Оролт
4 3 2 200
69 70 71 72
104 105 106 107
1 1
2 2
1 2
Гаралт
-1
Оролт
4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...