325C орчуулах · Codeforces.mn

# Мангасууд ба Алмаз
Пайгөрл нэг мангас болон мангасууд ба жигнэмэгүүдийн талаарх ном олсон. Тэр номыг уншиж байхдаа тус бүр нь $1$-c $n$ хүртэл дугаартай $n$ төрлийн мангас байдаг гэдгийг олж мэдсэн. Хэрвээ та мангасыг жигнэмэгээр хооллох юм бол мангас хэд хэдэн мангас (тэг ч байж болно) болон ядаж нэг өнгөлөг алмаз болон хуваагдана. Мангасууд олон янзаар хуваагдах боломжтой.

Эхлээд Пайгөрлд яг нэг мангас байна. Тэр мангасаа жигнэмэгээр хооллож эхлэнэ. Тэр мангасуудыг ямар ч мангас үлдэхгүй болтол хооллоно. Тэгээд тэр үүсссэн бүх алмазыг цуглуулна.

Танд ялгаатай мангасуудын хуваагдах аргыг тодорхойлсон хуваагдлын дүрмүүдийн жагсаалт өгөгдөнө. Мангас бүр ядаж нэг аргаар хуваагдаж чаддаг байх ба хэрвээ мангас хэд хэдэн аргаар хуваагдаж чаддаг байвал уг мангасыг хуваагдах бүрт Пайгөрл хуваагдах аргыг нь сонгож чадна.

Мангас бүрийн хувьд хэрвээ анх Пайгөрлд уг төрлийн нэг ширхэг мангас байсан гэвэл түүний цуглуулах боломжтой алмазын хамгийн бага болон хамгийн их тоог ол. Пайгөрлд хязгааргүй их жигнэмэг байгаа.

## Оролт
Эхний мөрөнд хоёр бүхэл тоо $m$ ба $n$ ($1 ≤ m, n ≤ 10^{5}$) байх ба боломжит хуваагдлуудын тоо болон мангасын ялгаатай төрлүүдийн тоо байна. Дараагийн $m$ мөр бүрт хуваагдлын дүрэм байна. Хуваагдлын дүрэм бүр мангасын төрлийн дугаар $m\_{i}$ ($1 ≤ m\_{i} ≤ n$) бүхэл тоогоор эхлэх ба тухайн мангасын хуваагдах мангасуудын тоо болон алмазын тоог илэрхийлэх $l\_{i}$ бүхэл тоогоор үргэлжилнэ. Үүний дараа $l\_{i}$ бүхэл тоо байх ба мангасын төрлийн дугаарыг агуулсан эерэг бүхэл тоонууд болон алмазыг илэрхийлсэн $-1$ тоонуудын дараалал байна.

Мангас бүрт ядаж нэг хуваагдлын дүрэм байна. Хуваагдлын дүрэм бүрт ядаж нэг алмаз байна. Бүх хуваагдлын дүрмүүдийн $l\_{i}$ нийлбэр нь хамгийн ихдээ $10^{5}$ байна.

## Гаралт
Мангас бүрийн хувьд тэдний төрлийн дугаарын дарааллын дагуу хоёр бүхэл тоотой мөр хэвлэ. Энэ мангасаар эхлэсэн тохиолдолд цуглуулж чадах алмазны хамгийн бага болон хамгийн их тоог хэвлэнэ. Хэрвээ Пайгөрл ямар ч мангасгүй үлдэх боломжгүй бол хамгийн бага болон хамгийн их утгууд дээр $-1$-г хэвлэ. Хэрвээ тэр дурын тооны алмаз цуглуулж чадахаар бол алмазны хамгийн их тоон дээр $-2$-г хэвлэ.

$314000000$-с их ямар ч тооны (гэхдээ хязгааргүй биш) хувьд уг тооны оронд $314000000$ тоог хэвлэ.

-- Г.Мэндбаяр

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

Оролт

6 4
1 3 -1 1 -1
1 2 -1 -1
2 3 -1 3 -1
2 3 -1 -1 -1
3 2 -1 -1
4 2 4 -1

Гаралт

Оролт

Гаралт

-1 -1
2 2