Longest Path in a DAG with Budget Constraint

You are given a Directed Acyclic Graph (DAG) with n nodes and m edges. Each node i (1 ≤ i ≤ n) has an associated visiting cost \(C_i\). Starting from any node, you can travel along directed edges. However, the cost of visiting any node after the starting node is added to your total cost, and this total must not exceed a given budget \(b\).

Your task is to determine the maximum number of edges in a valid path where the sum of the visiting costs (excluding the starting node) is \(\leq b\). If no edge can be taken without exceeding the budget, output -1.

Note: The path length is defined as the number of edges traveled. The nodes are numbered from 1 to n, and the visiting cost of the starting node is not counted toward the budget.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains three integers (n, m, b) (1 \le n, m, b \le 10^5), where:

   • (n) is the number of nodes,
   • (m) is the number of directed edges,
   • (b) is the available budget.

2. The second line contains (n) integers. The i-th integer represents the cost (C_i) for visiting node i.

3. Each of the following (m) lines contains two integers (u) and (v), representing a directed edge from node (u) to node (v).

outputFormat

Output a single integer to standard output (stdout): the maximum number of edges in a valid path such that the total visiting cost (excluding the starting node) does not exceed (b). If no valid path exists, output -1.## sample

5 6 10
2 3 5 4 3
1 2
1 3
2 4
3 4
4 5
2 5

3