A. Хувцас

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

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

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

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

Бяцхан Жералд хувцасны дэлгүүрт ороод бүх хувцаснууд нь хоорондоо зохицохгүй байгааг анзаарчээ. Жишээ нь Жералд костюм пиджак дээр бэйсболын малгай өмсвөл солиотой харагдах байв.

Дэлгүүрт $n$ хувцас байгаа бөгөөд тэдний яг $m$ нь хос л хоорондоо зохицдог. Бараа бүр өөрийн гэсэн үнэтэй. Жералд хоорондоо зохицох 3 хувцасыг хамгийн бага үнэтэй байхаар сонгохыг хүсэж байгаа.

Оролт

Эхний мөрөнд $n, m$ (enter image description here)тоонууд өгөгдөнө.

Дараагийн мөрөнд хувцас бүрийн үнийг тодорхойлох $a_i$ ($1 ≤ a_i ≤ 10^6$) тоонууд өгөгдөнө.

Дараагийн $m$ мөр бүрт $u_i$ болон $v_i$ ($1 ≤ u_i, v_i ≤ n, u_i ≠ v_i$) тоонууд өгөгдөнө. Энэ нь $u_i$ хувцас нь $v_i$ хувцастай зохицоно гэдгийг илэрхийлнэ. Бүх $u_i$ болон $v_i$ тоонууд ялгаатай байна.

Гаралт

Жералдын дэлгүүрт төлөх хамгийн бага мөнгийг хэвлэ. Хэрвээ дэлгүүрт хоорондоо зохицох 3 хувцас байхгүй тохиолдолд "-1"-ийг хашилтгүйгээр хэвлэ.

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

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

Оролт
3 3
1 2 3
1 2
2 3
3 1
Гаралт
6
Оролт
3 2
2 3 4
2 3
2 1
Гаралт
-1
Оролт
4 4
1 1 1 1
1 2
2 3
3 4
4 1
Гаралт
-1

Тэмдэглэл

In the first test there only are three pieces of clothing and they all match each other. Thus, there is only one way -- to buy the 3 pieces of clothing; in this case he spends 6 roubles.

The second test only has three pieces of clothing as well, yet Gerald can't buy them because the first piece of clothing does not match the third one. Thus, there are no three matching pieces of clothing. The answer is -1.

In the third example there are 4 pieces of clothing, but Gerald can't buy any 3 of them simultaneously. The answer is -1.

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