You are given an integer n representing the number of vertices in a directed acyclic graph, labeled from $0$ to n $- 1$. You are also given a $2$D integer array edges, where edges[i] = [u_i, v_i, w_i] denotes a directed edge from vertex u_i to vertex v_i with weight w_i.

Additionally, you are given two integers k and t.

Find the maximum possible sum of edge weights for any path in the graph that contains exactly k edges such that the total sum of weights is strictly less than t.

Return the maximum sum of weights among all valid paths. If no such path exists, return $-1$.

Constraints:

• $1 \leq$ n $\leq 300$

• $0 \leq$ edges.length $\leq 300$

• edges[i] = [u_i, v_i, w_i]

• $0 \leq$ u_i, v_i $<$ n

• u_i $\neq$ v_i

• $1 \leq$ w_i $\leq 10$

• $0 \leq$ k $\leq 300$

• $1 \leq$ t $\leq 600$

• The input graph is guaranteed to be a DAG.

• There are no duplicate edges.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.