The items in the same strongly-connected component can be picked up when visiting it for the first time. Therefore, we can merge each strongly-connected component into one to assume the graph as a DAG (Directed Acyclic Graph).

Hereinafter we assume that the graph is a DAG, and Vertices \(1, 2, \dots,\) and \(N\) are sorted topologically. The problem can be boiled down to a minimum-cost flow problem.

You may first come up with the following way:

• For \(1 \leq u \leq N\), prepare vertices \(\mathrm{in}_u, \mathrm{out}_u\). Also, prepare \(S\) and \(T\) as the source and the sink.
• For \(1 \leq u \leq N\), add an edge from \(\mathrm{in}_u\) to \(\mathrm{out}_u\) with capacity \(1\) and cost \(-X_u\), and another edge with capacity \(\infty\) and cost \(0\).
• For every edge \((u, v)\), add an edge from \(\mathrm{out}_u\) to \(\mathrm{in}_v\) with capacity \(\infty\) and cost \(0\).
• Add an edge from \(S\) to \(\mathrm{in}_1\) with capacity \(\infty\) and cost \(0\).
• For \(1 \leq u \leq N\), add an edge from \(\mathrm{out}_u\) to \(T\) with capacity \(\infty\) and cost \(0\).
• The answer is the minimum cost from \(S\) to \(T\) of flow \(K\), multiplied by \(-1\).

However, this method gives rise to edges with negative costs. We can remove the negative edges as follows:

• For \(1 \leq u \leq N\), add an edge from \(\mathrm{in}_u\) to \(\mathrm{out}_u\) with capacity \(1\) and cost \(0\), and another edge of capacity \(\infty\) and cost \(X_u\).
• For every edge \((u, v)\), add an edge from \(\mathrm{out}_u\) to \(\mathrm{in}_v\) with capacity \(\infty\) and cost \(X_{u + 1} + \dots + X_{v - 1}\).
• Add an edge from \(S\) to \(\mathrm{in}_1\) with capacity \(\infty\) and cost \(0\).
• For \(1 \leq u \leq N\), add an edge from \(\mathrm{out}_u\) to \(T\) with capacity \(\infty\) and cost \(X_{u + 1} + \dots + X_N\).
• The answer is the minimum cost from \(S\) TO \(T\) of flow \(K\), subtracted from \(K \left(\sum_u X_u \right)\).

Sample code (C++)