Zadanie z tego laboratorium stanowi pretekst do przypomnienia i rozszerzenia wiadomości o bibliotece STL, w szczególności pokazania, w jaki sposób można wykorzystywać jej kontenery i metody do pisania efektywnych programów (efektywnych z algorytmicznego punktu widzenia). Bardzo wygodna jest, na przykład, reprezentacja grafu rzadkiego w tablicy vectorów bądź list (realizacja list sąsiedztwa).
Zadanie PRJ (Projekty)
Dostępna pamięć: 256MB.
Bajtazar właśnie awansował na szefa działu informatyki Bardzo Ważnej Instytucji Państwowej. W jego obowiązkach jest zarządzanie projektami informatycznymi. Instytucja przygotowała listę potencjalnych projektów, które powinny zostać wykonane. Niestety wykonanie niektórych projektów zależy od pomyślnego wykonania innych. Dodatkowo, każdy projekt charakteryzuje się minimalną liczbą programistów, którzy są konieczni do jego wykonania.
Ze względu na cięcia budżetowe nie jest możliwe wykonanie wszystkich projektów. Zarząd zdecydował, że zrealizowane zostanie jedynie \( \displaystyle k \) projektów. Bajtazar dostał polecenie zatrudnienia minimalnej liczby programistów, którzy są konieczni do zrealizowania co najmniej \( \displaystyle k \) projektów (przy czym projekty mogą być realizowane sekwencyjnie, tak że programiści są przenoszeni z jednego projektu do drugiego).
Napisz program, który pomoże Bajtazarowi i wyznaczy minimalną liczbę programistów, których należy zatrudnić.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczba całkowite \( \displaystyle n \), \( \displaystyle m \) i \( \displaystyle k \) ( \( \displaystyle 1 \leq n \leq 100\,000 \), \( \displaystyle 0 \leq m \leq 500\,000 \), \( \displaystyle 0 \le k \le n \) ), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę projektów, liczbę zależności pomiędzy projektami oraz minimalną liczbę projektów, które należy zrealizować. W kolejnych \( \displaystyle n \) wierszach zostały zapisane informacje o liczbie programistów koniecznych do wykonania projektów. W \( \displaystyle (i+1) \)-szym wierszu została zapisana liczba całkowita \( \displaystyle p_i \) ( \( \displaystyle 1\le p_i \le 100\,000\,000 \) ) oznaczająca, że do wykonania \( \displaystyle i \)-tego projektu konieczne jest zatrudnienie \( \displaystyle p_i \) programistów. W kolejnych \( \displaystyle m \) wierszach zostały zapisane informacje o zależnościach pomiędzy projektami. Każdy z tych wierszy zawiera dwie liczby całkowite \( \displaystyle a \), \( \displaystyle b \) ( \( \displaystyle 1\le a,b \le n \), \( \displaystyle a\ne b \) ) oddzielone pojedynczym odstępem i oznaczające, że do wykonania projektu \( \displaystyle a \) konieczne jest ukończenie projektu \( \displaystyle b \).
Możesz założyć, że zależności pomiędzy projektami nie tworzą cykli.
Wyjście
W jedynym wierszu standardowego wyjścia należy wypisać minimalną liczbę programistów, których należy zatrudnić, tak by było możliwe wykonanie \( \displaystyle k \) projektów.
Przykład
Dla danych wejściowych:
5 3 3
10
500
150
200
100
1 2
1 3
4 5
poprawnym wynikiem jest:
200