Find the problem directly seems very difficult. Instead, let us perform binary search.

In order to do binary search, it is sufficient to solve the following problem:

We perform the operation described in the Problem Statement $N$ times. However, the cost of every operation should be at most $X$. Is it possible to perform all the $N$ operations?

Here is an important fact: if the cost of the vertex is less than or equal to \(X\), then it remains less than or equal to \(X\) later on.

Therefore, we can solve the problem by the following greedy algorithm:

• Maintain a stack $s$, which is initially empty.
• Insert to $s$ all vertices that we can perform operations on.
• While $s$ is not empty, repeat the following operation:
• Take one vertex $v$ from $s$. Remove $v$ from $s$.
• For each vertex that is not removed yet, decrease the cost required for an operation by $A_v$.
• Insert to $s$ the vertices on which the operation is determined to cost at most $X$.
• If all vertices can be removed by the operations, it is possible; otherwise, it is impossible.

Therefore, the answer for the original problem can be solved by solving the subpromblem above \(O(\log(N \times \max A))\) times.

The complexity is \(\mathrm{O}((N+M)\log(N \times \max A))\).