D. Дима ба урхитай граф

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

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

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

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

Дима, Инна хоёр хамтдаа цагийг өнгөрөөх дуртай. Асуудлын гол нь Серёжа зарим шалтгаанаар өрөөнөөсөө гарах тийм ч дуртай биш. Гэвч Дима, Инна хоёр бие биендээ их хайртай учир тэд заль зохиохоор шийдсэн.

Дима урхитай граф байгуулсан. Тэр өрөөний найзынхаа сонирхлыг татахын тулд "Хээе Серёжа миний гоё графыг хараач" гэж орилсон ба түүнийг эхний зангилааруу түлхэн оруулсан.

Урхитай граф нь $n$ зангилаа $m$ ирмэгээс бүрдэх чиглэлгүй граф байна. $k$ дугаартай ирмэгийн хувьд Дима $l_{k}$-с $r_{k}$ $(l_{k} ≤ r_{k})$ хүртэлх бүхэл тоон олонлогийг тэмдэглэсэн. Урхитай графаас гарахын тулд эхлээд Серёжа нэг бүхэл тоо (үүнийг $x$ гэе) сонгох хэрэгтэй (үйлдэл хийж эхлэхээс өмнө), тэгээд Серёжа $1$ дугаартай эхлэх зангилаанаас эцсийн $n$ дугаартай зангилаа хүртэл явах ёстой. Энд Серёжа $l_{k} ≤ x ≤ r_{k}$ байвал л $k$ ирмэгийн дагуу явж болно.

Серёжа бол математикч. Серёжа $1$-р зангилаанаас $n$-р зангилаа хүрэх нэг замын найдвартай байдлыг бүхэл тоонуудын тоо $x$-р тодорхойлсон. Энд хэрвээ Серёжа анх эдгээр тоонуудын аль нэгийг сонгосон бол замыг бүхэлд нь туулна. Серёожад түүнийг өрөөнд нь аль болох хурдан аваачих мөн хамгийн өндөр найдвартай замыг олоход туслана уу.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ $(2 ≤ n ≤ 10^{3}, 0 ≤ m ≤ 3*10^{3})$ байна. Тэгээд ирмэгүүдийг тодорхойлсон $m$ мөр байна. Мөр бүрт $a_{k}$, $b_{k}$, $l_{k}$ ба $r_{k}$ $(1 ≤ a_{k}, b_{k} ≤ n, 1 ≤ l_{k} ≤ r_{k} ≤ 10^{6})$ дөрвөн бүхэл тоо байна. Эдгээр тоонууд нь урхитай графын $k$-р ирмэг нь $a_{k}$ ба $b_{k}$ зангилаануудыг холбох ба энэ ирмэг нь $l_{k}$-с $r_{k}$ хүртэлх бүхэл тоонуудын хүрээтэй харгалзана гэдгийг илэрхийлнэ.

Өгөгдсөн граф нь зангилааг өөртэй нь холбосон ирмэгүүд болон давхар ирмэгтэй байж болно.

Гаралт

Гаралтын нэг мөрөнд эхний зангилаанаас $n$-р зангилаа хүртэлх бүх замуудын дундаас хамгийн өндөр найдварыг илэрхийлэх бүхэл тоог хэвлэ. Хэрвээ ийм замууд олдохгүй эсвэл хамгийн өндөр найдвар нь 0-тэй тэнцүү байвал нэг мөрөнд "$Nice work, Dima!$" гэсэн өгүүлбэрийг хашилтгүйгээр хэвлэ.

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

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

Оролт
4 4
1 2 1 10
2 4 3 5
1 3 1 5
2 4 2 7
Гаралт
6
Оролт
5 6
1 2 1 10
2 5 11 20
1 4 2 5
1 3 10 11
3 4 12 10000
4 5 6 6
Гаралт
Nice work, Dima!

Тэмдэглэл

Эхний жишээг тайлбарлая.

Нийтдээ бидэнд 1-с 4-р зангилааруу явах хоёр зам байна: эхнийх нь та [1-10] хүрээ бүхий 1-2 ирмэгийн дагуу явах ёстой тэгээд 2-4 хооронд байгаа хоёр ирмэгийн аль нэгээр явна.

Эдгээрийн нэг нь [3-5] хүрээг агуулж байна, бид 3, 4, 5 дугааруудаар дайрч болно. Ингээд найдвартай байдал нь 3.

Хэрвээ бид [2-7] хүрээ бүхий 2-4 ирмэгийн дагуу явах юм бол бид 2, 3, 4, 5, 6, 7 тоонуудаар дайрна. Ингээд найдвартай байдал нь 6 учир зөв хариулт юм.

1-2 ирмэг нь хариултанд нөлөөлөхгүй учир нь энэ ирмэгийн хүрээ нь дараах ирмэгүүдийн аль алиных нь хүрээг агуулж байна.

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