Ciasta [A]
Limit pamięci: 256 MB
Na tegorocznym zjeździe bajtockich cukierników zjawili się mistrzowie wypieków z całego kraju.
W ramach zjazdu odbędzie się konkurs na najlepsze ciasto upieczone przez trzyosobowy zespół ciastkarzy.
Każda trójka może zgłosić co najwyżej jedno ciasto, jednak każdy uczestnik może należeć do wielu zespołów.
Niestety niektórzy cukiernicy się nie lubią i nie chcą razem piec ciasta.
Dla każdego zawodnika wiemy, ile dekagramów mąki potrzebuje do upieczenia ciasta.
Trzyosobowy zespół zużywa tyle mąki, ile jego członek o największym zapotrzebowaniu.
Ile mąki zostanie zużyte podczas zawodów, jeśli każda trójka cukierników, w której wszyscy się lubią, piecze dokładnie jedno ciasto?
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i (, ),
oddzielone pojedynczym odstępem i oznaczające liczbę cukierników na zjeździe oraz liczbę par, które lubią się wzajemnie.
Uczestnicy zjazdu są ponumerowani od do .
Drugi wiersz zawiera liczb całkowitych (), pooddzielanych pojedynczymi odstępami
i określających zapotrzebowania poszczególnych cukierników na mąkę (w dekagramach).
Następne wierszy zawiera informacje o parach zawodników, którzy się lubią.
W każdym z tych wierszy znajdują się dwie liczby całkowite i (), oddzielone pojedynczym
odstępem.
Oznaczają one, że cukiernicy i wzajemnie się lubią.
Zakładamy, że wszystkie pary uczestników zjazdu poza wymienionymi na wejściu nie chcą razem piec ciasta.
Każda para cukierników pojawia się na wejściu co najwyżej raz.
Wyjście
W pierwszym i jedynym wierszu standardowego wejścia wypisz jedną liczbę całkowitą -
ilość mąki, jaką zużyją w sumie wszystkie zespoły, w dekagramach.
Przykład
Dla danych wejściowych:
5 7
1 5 3 4 2
1 2
2 3
5 2
4 3
3 1
1 4
5 1
poprawną odpowiedzią jest:
14
Wyjaśnienie do przykładu.
Trzyosobowe zespoły w składach , i
potrzebują do upieczenia ciast odpowiednio 5, 5 i 4 dag mąki.
W sumie potrzeba dag mąki.
Autor zadania: Jakub Łącki.