B. Шатлал

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

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

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

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

Ник-ын компани $n$ тооны ажилтантай. Ник «дээд шатлалын ажилтан-доод шатлалын ажилтан» гэсэн шатлалын модыг бий ёстой (энэ нь нэгээс бусад ажилтан бүрт дээд шатны нэг хянагч байна гэсэн үг юм). Доорх хүснэгтэнд $m$ тооны өргөдөл бүртгэгдсэн ба «ажилтан $a_{i}$ нэмэлт $c_{i}$ хөлсөөр $b_{i}$ ажилтны дээд шатны хянагч ажилтан болоход бэлэн байгаа.» Ажилтан бүрийн $q_{j}$ мэргэжил тодорхой байгаа ба өргөдөл гаргагчийн хувьд дараах илэрхийлэл үнэн болно: $q_{a_{i}} > q_{b_{i}}$. Ийм шатлал бий болгоход гарах хамгийн бага зардал гаргахад Никд тусла эсвэл үүнийг бодож олох боломжгүй гэдгийг батал.

Оролт

Эхний оролтын мөр нь тус компани дахь нийт ажилчдын тоог харуулсан $n$ ($1 ≤ n ≤ 1000$) гэсэн бүхэл тоог агуулна. Дараагийн мөр хүлээн авсан өргөдлийн тоог илэрхийлсэн $m$ ($0 ≤ m ≤ 10000$) гэсэн тоог агуулж байна. Дараагийн $m$ мөр нь өргөдлүүдийг илэрхийлж байгаа ба эдгээр нь гурван зайгаар тусгаарласан тоонуудын хэлбэрт байна: $a_{i}$, $b_{i}$ and $c_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $0 ≤ c_{i} ≤ 10^{6}$). Өргөдлүүд өөр хоорондоо ижил байж болно. Өөрөөр хэлбэл хоёр ажилтнаас ирсэн өргөдөл хоёулаа нэг ажилтны удирдах дээд шатны хянагч болохыг хүссэн байж болох ба тэдний санал болгосон үнэ өөр байж болно. Өргөдөл бүр $q_{a_{i}} > q_{b_{i}}$.

Гаралт

Ийм шатлалыг бий болгохын тулд хамгийн багадаа хичнээн хэмжээний зардал гарахыг харуулсан цорын ганц мөрийг гарга. Хэрэв энэ боломжгүй бол $-1$ гарга.

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

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

Оролт
4
7 2 3 1
4
1 2 5
2 4 1
3 4 1
1 3 5
Гаралт
11
Оролт
3
1 2 3
2
3 1 2
3 1 3
Гаралт
-1

Тэмдэглэл

Эхний загварт шатлалыг бий болгох хамгийн боломжит арга нь өргөдлүүдийг 1, 2, 4 гэх мэтчилэн индекстэй авч үзсэнээр 11 хүрэхэд хамгийн бага нийт зардал гарч байгаа юм. Хоёр дахь загварт шатлал бий болгох боломжгүй учир хариу -1$ байна.

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