Lesson 6

Programming problem. Implement a solution for the project selection problem. The first line contains integers \(1 \le n \le 40\) and \(1 \le m \le 1000\). We assume that the projects are called \([n]\). The next \(n\) lines contain the profit value \(p_{1}, \dotsc, p_{n}\) of \(n\) projects. Each of the following \(m\) lines defines a constraint \((i,j)\): if one performs the project \(i\), one also needs to perform the project \(j\). Output the maximum profit of a feasible set of projects.

7 7
5
3
2
4
-4
-7
-2
1 4
1 6
2 4
2 5
3 5
4 7
5 7

3