E. Шугаман вант улсын уралдаан

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

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

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

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

Та машины уралдаан зохион байгуулагч бөгөөд Шугаман вант улсад машины уралдаан зохион байгуулах гэж байгаа. Шугаман Вант Улсад зүүнээс баруун тийш сунан баригдсан дараалсан $n$ тооны зам байдаг. Замууд нь тооны өсөх дарааллаар $1$-ээс $n$ хүртэл эрэмбэлэгдсэн байна. Эдгээр замууд дээр хэд хэдэн уралдаан болж магадгүй. Уралдаан тус бүр эдгээр замуудын дараалсан дэд хэсгийг ашиглах юм. Уралдаан болсон замуудын төлбөр болгож тодорхой хэмжээний мөнгө төлөх болно. Цаг хугацааны хувьд давхцах уралдаан байхгүй учир зарим замыг хэд хэдэн уралдаанд ашиглаж болно.

Харамсалтай нь зарим замын чанар муудсан учир засах шаардлагатай байгаа. Зам тус бүрийг засах зардлыг та төлөх ёстой. Хэрэв уралдаанд ашиглах бүх замуудыг зассан тохиолдолд тухайн замуудыг уралдаанд ашиглана. Таны даалгавар өөрийн чинь ашгийг нэмэх тэдгээр замуудыг (бүгдийг эсвэл аль ч биш) засах явдал юм. Уралдаанаас авсан мөнгөнөөс зам зассан мөнгийг хасаад гарсан дүн нь таны олох ашиг байх болно. Та ямар ч зам засалгүйгээр 0 төгрөгийн ашиг авж болно гэдгийг анхаарна уу.

Таны олж чадах хамгийн их ашиг хэд байхыг хэвлэ.

Оролт

Оролтын эхний мөрөнд өөр хоорондоо зайгаар тусгаарлагдсан $n$ болон $m$ ($1 ≤ n, m ≤ 2*10^{5}$) гэсэн хоёр бүхэл тоо агуулах ба эдгээр нь нийт замын тоо болон уралдааны тоог тус тус харуулна.

Дараагийн $n$ мөрүүд нь $10^{9}$-ээс хэтрэхгүй, сөрөг биш ганц бүхэл тоо агуулах ба энэ нь зам засах өртгийг харуулна. Зам засах өртөг нь $1$ замаас $n$ зам хүртэл дарааллаар өгөгдсөн байна.

Сүүлийн $m$ мөрүүд тус бүр нь хоорондоо зайгаар тусгаарлагдсан гурвалсан хос бүхэл тоог агуулна. гурвалсан хос тоо тус бүр нь $lb$, $ub$, $p$ ($1 ≤ lb ≤ ub ≤ n, 1 ≤ p ≤ 10^{9}$) байдлаар өгөгдөх ба энэ гурван тооны төлөөлж буй уралдаан нь $lb$-ээс $ub$ хүртэл зам дээр болно гэдгийг илэрхийлэх ба уралдаан тус зам дээр болвол та $p$ төгрөг авна.

Гаралт

Таны авч болох хамгийн их ашгийг харуулсан бүхэл тоо хэвлэнэ үү.

C++ дахь 64 бит бүхэл тоог унших болох бичихдээ %lld нарийвчлал ашиглахгүйг анхаарна уу. Үүний оронд cout хэсгийг ашиглах нь зүйтэй (мөн %I64d ашиглаж болно).

Орчуулсан: Энхгэрэл

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

Оролт
7 4
3
2
3
2
1
2
3
1 2 5
2 3 5
3 5 3
7 7 5
Гаралт
4
Оролт
2 1
0
3
1 2 5
Гаралт
2
Оролт
3 1
10
10
10
1 3 10
Гаралт
0

Тэмдэглэл

Эхний жишээнд хамгийн тохиромжтой арга бол $1$, $2$, $3$, $7$ гэсэн замуудыг засах явдал юм. Ингээд таньд $15$ төлөх гурван уралдаан энэ замууд дээр болно. Та дээрх замуудыг засахад $11$ зарцуулсан бол таны ашиг $4$ байна.

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