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

Олонлог эгзэ сургуульд нийт n сурагчтай. Зарим сурагчид хоорондоо найзууд бөгөөд нийт m найзын холбоо өгөгдөнө.

Сургуулийн сурагч бүр шатрын тэмцээнд оролцож байсан бөгөөд тодорхой рэтинг оноотой (чадварыг илрэхийлэх).

Тэмцээн нь дараах дүрмийг баримтлах ёстой.

• Тэмцээнд шууд найзуудыг сонгон оруулахгүй(Өөрөөр хэлбэл шууд найз байхгүй байх ёстой)
• Багийн сурагчдын тоо нь хамгийн ихдээ K байх ёстой

Зорилго:

Сонгосон сурагчдын рэтинг онооны нийлбэрийг хамгийн их байлгах багийг сонгох шаардлагатай болсон. Та туслаж чадах уу?

Оролт:

Эхний мөрөнд сурагчдын тоо болох n, найзын холбоог илэрхийлэх m, багийн гишүүдийн хамгийн их байх тоог илэрхийлэх k тоо гэсэн 3 бүхэл тоо хоосон зайгаар тусгаарлан өгөгдөнө.

Хоёр дахь мөрөнд сурагч бүрийн рэтинг оноог илэрхийлэх a1, a2, .., an гэсэн n ширхэг бүхэл тоо хоосон зайгаар тусгаарлан өгөгдөнө

Дараагийн m ш мөр тус бүрд u v гэсэн 2 бүхэл тоо байх ба эдгээр нь u, v сурагчид найзууд гэдгийг илэрхийлнэ

Гаралт:

Гаралтын файлд сонгож болох k -аас цөөн хүнтэй багуудаас рэтинг онооны нийлбэр нь хамгийн их байх багийн онооны нийлбэрийг илэрхийлэх нэг бүхэл тоо байна.

Хязгаарлалтууд:

• \(1 ≤ n ≤ 100000\)
• \(0 ≤ m ≤ 100000\)
• \(1 ≤ k ≤ n\)
• \(0 ≤ a[i] ≤ 10^4\)

Дэд бодлого

Жишээ:

Оролт-1

3 2 2
3 2 3
1 2
2 3

Гаралт-1

6

Тайлбар-1

? Тайлбар 1 ба 2 найз → хамт авч болохгүй 2 ба 3 найз → хамт авч болохгүй

? Боломжууд:

(1,3) → 3 + 3 = 6 ✅ (2) → 2

? Хамгийн их = 6

Оролт-2

5 3 2
5 1 2 6 4
1 2
2 3
4 5

Гаралт-2

11

Тайлбар-2

4 ба 5 найз → хамт авч болохгүй 1–2–3 холбоотой

? Боломж:

4 (6 оноо) + 1 (5 оноо) = 11 ✅