Problem Narrative

You’re building a fintech payout orchestrator that routes money transfers through external banking partners. Each partner has different reliability and processing latency. When a partner is down, you can reroute through other partners, but every hop adds time and may incur contractual penalties. At millions of payouts/day, choosing the wrong route can cause SLA breaches and direct revenue loss.

Formal Problem Statement

You are given a directed graph of partners. Each directed edge represents an integration from partner u to partner v with:

• time: milliseconds added if you route through that integration
• penalty: an integer penalty score (e.g., risk/compliance overhead)

You must route a payout from source to target with total time ≤ max_time.

Return the minimum total penalty among all valid routes. If no route can satisfy the time limit, return -1.

Input

• n: number of partners labeled 0..n-1
• edges: list of [u, v, time, penalty] directed edges
• source, target: integers
• max_time: integer

Output

• Minimum achievable total penalty under the time constraint, else -1.

Examples

Example 1

• Input: n = 4, edges = [[0,1,5,3],[1,3,5,2],[0,2,6,1],[2,3,4,10]], source = 0, target = 3, max_time = 10
• Output: 5
• Explanation: Route 0 -> 1 -> 3 has time 5+5=10 and penalty 3+2=5. Route 0 -> 2 -> 3 has time 6+4=10 but penalty 1+10=11, so 5 is minimal.

Example 2

• Input: n = 3, edges = [[0,1,8,1],[1,2,8,1]], source = 0, target = 2, max_time = 10
• Output: -1
• Explanation: The only path takes time 16, which exceeds max_time.

Constraints

• 1 <= n <= 2 * 10^4
• 0 <= edges.length <= 2 * 10^5
• 0 <= u, v < n, u != v
• 1 <= time <= 10^4
• 0 <= penalty <= 10^4
• 0 <= max_time <= 10^7

Notes / Clarifications

• The graph may contain cycles.
• Penalties and times are additive.
• If source == target, the answer is 0 (empty route) as long as 0 <= max_time.