704D орчуулах · Codeforces.mn

# Ахмад Америк
Стев Рожерс-д S.H.I.E.L.D-ээс түүнд өгсөн шинэ вибраниум бамбайнуудад ихээхэн таалагджээ. Тэдгээр бамбайнууд нь бүгд будагдаагүй байв. Нийт $n$ ширхэг бамбай байгаа бөгөөд $i$-дахь бамбай нь координатын хавтгайн $(x\_{i}, y\_{i})$ гэсэн цэг дээр байрласан байх ажээ. Түүнчлэн 2 болон түүнээс олон тооны бамбайнууд нь нэг ижил байрлал дээр байх боломжтой юм.

Стев эдгээр бүх бамбайнуудыг будахыг хүсжээ. Тэрээр бамбай бүрийг улаан эсвэл цэнхэр өнгөөр будах юм. Нэг бамбайг улаанаар будахад $r$ долларын өртөгтэй бөгөөд цэнхрээр будахад $b$ долларын өртөгтэй байх ажээ.

Түүнчлэн Стев $m$ ширхэг нөхцөлийг хангаж байхаар будахыг хүсэж байв. $i$-дахь нөхцөл нь $t\_{i}$, $l\_{i}$ болон $d\_{i}$ гэсэн 3 бүхэл тоогоор өгөгдөнө:

* Хэрэв $t\_{i} = 1$ байвал, $x = l\_{i}$ гэсэн шулуун дээрх улаан болон цэнхэр бамбайн тоонуудын абсолют зөрүү нь $d\_{i}$-аас хэтрэхгүй байх ёстой.
  * Хэрэв $t\_{i} = 2$ байвал, $y = l\_{i}$ гэсэн шулуун дээрх улаан болон цэнхэр бамбайн тоонуудын абсолют зөрүү нь $d\_{i}$-аас хэтрэхгүй байх ёстой.

Стев таныг эдгээр бүх нөхцөлийг хангаж байх, нийт өртөг нь хамгийн бага байх будалтыг олж өгөхийг хүсжээ.
 
## Оролт
Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 100 000$) өгөгдөх ба эдгээр нь харгалзан бамбайн тоо болон нийт нөхцөлийн тоог илэрхийлнэ.

2-дахь мөрөнд 2 бүхэл тоо $r$ болон $b$ ($1 ≤ r, b ≤ 10^{9}$) өгөгдөнө.

Дараагийн $n$ мөрөнд бамбайнуудын координатууд өгөгдөнө. Эдгээр мөрүүдийн $i$-дахь мөрөнд 2 бүхэл тоо $x\_{i}$ болон $y\_{i}$ ($1 ≤ x\_{i}, y\_{i} ≤ 10^{9}$) өгөгдөнө.

Дараагийн $m$ мөрөнд бодлогын нөхцөлүүд өгөгдөнө. Эдгээр мөрүүдийн $j$-дэх мөрөнд 3 бүхэл тоо $t\_{j}$, $l\_{j}$ болон $d\_{j}$ ($1 ≤ t\_{j} ≤ 2, 1 ≤ l\_{j} ≤ 10^{9}, 0 ≤ d\_{j} ≤ n$) өгөгдөнө.

## Гаралт
Хэрэв бүх нөхцөлийг хангах будалт оршин байхгүй бол гаралтын эхний мөрөнд -1 гэж хэвлэнэ үү.

Бусад тохиолдолд гаралтын эхний мөрөнд хамгийн бага нийт өртгийн хэмжээг хэвлэнэ үү. 2-дахь мөрөнд зөвхөн 'r' болон 'b' гэсэн үсгүүдээс тогтох $n$ урттай нэгэн тэмдэгт мөрийг хэвлэнэ. Уг тэмдэгт мөрийн $i$-дахь тэмдэгт нь хэрэв $i$-дахь бамбай нь оновчтой хариултын явцад улаанаар будагдах ёстой бол 'r' байх бөгөөд хэрэв $i$-дахь бамбай нь оновчтой хариултын явцад цэнхрээр будагдах ёстой бол 'b' байх юм. Эдгээр өнгүүдээр бамбайнуудыг будах өртөг нь эхний мөрөнд таны хэвлэсэн хамгийн бага нийт өртөгтэй тэнцүү байх ёстойг анхаарна уу.

Хэрэв нэгээс олон оновчтой хариулт байвал тэдгээрийн алийг нь ч хэвлэсэн болно.

-- Баатархүү

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

Оролт

Гаралт

25
rbrbb

Оролт

Гаралт

-1