Проекты для Иссык-Кульской области
Акимат Иссык-Кульской области выбирает проекты на следующий год. Всего предложено n проектов, проект i принесёт области доход p[i] тысяч сомов (если p[i] отрицательно — это затраты: дороги, водопровод, школы). Проекты зависят друг от друга: пара (a, b) означает, что проект a можно делать, только если делается и проект b (например, гостевой дом в Бостери требует водопровода).
Выберите набор проектов, в котором для каждого выбранного проекта выбраны и все проекты, от которых он зависит, а суммарный доход наибольший. Пустой набор тоже допустим.
Входные данные
В первой строке — два целых числа n и m (1 ≤ n ≤ 5000, 0 ≤ m ≤ 10⁵). Во второй строке — n целых чисел p[1], …, p[n] (|p[i]| ≤ 10⁹). В каждой из следующих m строк — пара различных чисел a b (1 ≤ a, b ≤ n): проект a требует проекта b. Зависимости могут образовывать циклы.
Выходные данные
Выведите наибольший суммарный доход.
Пример 1
Вход:
5 4
12 3 -5 -3 -8
1 3
1 4
2 5
3 4
Выход:
4
Пояснение
Выгодно сделать проекты 1, 3 и 4: 12 − 5 − 3 = 4. Проект 2 даёт 3, но требует проекта 5 (−8), поэтому его брать невыгодно.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 15.
Комментарии