Проекты для Иссык-Кульской области


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Акимат Иссык-Кульской области выбирает проекты на следующий год. Всего предложено 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.


Комментарии

Еще нет ни одного комментария.