bowang0911/leetcode huggingface dataset:
Remove One Element to Make the Array Strictly Increasing

Given a **0-indexed** integer array `nums`, return `true` _if it can be made **strictly increasing** after removing **exactly one** element, or_ `false` _otherwise. If the array is already strictly increasing, return_ `true`.

The array `nums` is **strictly increasing** if `nums[i - 1] < nums[i]` for each index `(1 <= i < nums.length).`

**Example 1:**

**Input:** nums = \[1,2,10,5,7\]
**Output:** true
**Explanation:** By removing 10 at index 2 from nums, it becomes \[1,2,5,7\].
\[1,2,5,7\] is strictly increasing, so return true.

**Example 2:**

**Input:** nums = \[2,3,1,2\]
**Output:** false
**Explanation:**
\[3,1,2\] is the result of removing the element at index 0.
\[2,1,2\] is the result of removing the element at index 1.
\[2,3,2\] is the result of removing the element at index 2.
\[2,3,1\] is the result of removing the element at index 3.
No resulting array is strictly increasing, so return false.

**Example 3:**

**Input:** nums = \[1,1,1\]
**Output:** false
**Explanation:** The result of removing any element is \[1,1\].
\[1,1\] is not strictly increasing, so return false.

**Constraints:**

*   `2 <= nums.length <= 1000`
*   `1 <= nums[i] <= 1000`
Remove All Occurrences of a Substring

Given two strings `s` and `part`, perform the following operation on `s` until **all** occurrences of the substring `part` are removed:

*   Find the **leftmost** occurrence of the substring `part` and **remove** it from `s`.

Return `s` _after removing all occurrences of_ `part`.

A **substring** is a contiguous sequence of characters in a string.

**Example 1:**

**Input:** s =  "daabcbaabcbc ", part =  "abc "
**Output:**  "dab "
**Explanation**: The following operations are done:
- s =  "da**abc**baabcbc ", remove  "abc " starting at index 2, so s =  "dabaabcbc ".
- s =  "daba**abc**bc ", remove  "abc " starting at index 4, so s =  "dababc ".
- s =  "dab**abc** ", remove  "abc " starting at index 3, so s =  "dab ".
Now s has no occurrences of  "abc ".

**Example 2:**

**Input:** s =  "axxxxyyyyb ", part =  "xy "
**Output:**  "ab "
**Explanation**: The following operations are done:
- s =  "axxx**xy**yyyb ", remove  "xy " starting at index 4 so s =  "axxxyyyb ".
- s =  "axx**xy**yyb ", remove  "xy " starting at index 3 so s =  "axxyyb ".
- s =  "ax**xy**yb ", remove  "xy " starting at index 2 so s =  "axyb ".
- s =  "a**xy**b ", remove  "xy " starting at index 1 so s =  "ab ".
Now s has no occurrences of  "xy ".

**Constraints:**

*   `1 <= s.length <= 1000`
*   `1 <= part.length <= 1000`
*   `s`​​​​​​ and `part` consists of lowercase English letters.
Maximum Alternating Subsequence Sum

The **alternating sum** of a **0-indexed** array is defined as the **sum** of the elements at **even** indices **minus** the **sum** of the elements at **odd** indices.

*   For example, the alternating sum of `[4,2,5,3]` is `(4 + 5) - (2 + 3) = 4`.

Given an array `nums`, return _the **maximum alternating sum** of any subsequence of_ `nums` _(after **reindexing** the elements of the subsequence)_.

A **subsequence** of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, `[2,7,4]` is a subsequence of `[4,2,3,7,2,1,4]` (the underlined elements), while `[2,4,2]` is not.

**Example 1:**

**Input:** nums = \[4,2,5,3\]
**Output:** 7
**Explanation:** It is optimal to choose the subsequence \[4,2,5\] with alternating sum (4 + 5) - 2 = 7.

**Example 2:**

**Input:** nums = \[5,6,7,8\]
**Output:** 8
**Explanation:** It is optimal to choose the subsequence \[8\] with alternating sum 8.

**Example 3:**

**Input:** nums = \[6,2,1,2,4,5\]
**Output:** 10
**Explanation:** It is optimal to choose the subsequence \[6,1,5\] with alternating sum (6 + 5) - 1 = 10.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 105`
Maximum Product Difference Between Two Pairs

The **product difference** between two pairs `(a, b)` and `(c, d)` is defined as `(a * b) - (c * d)`.

*   For example, the product difference between `(5, 6)` and `(2, 7)` is `(5 * 6) - (2 * 7) = 16`.

Given an integer array `nums`, choose four **distinct** indices `w`, `x`, `y`, and `z` such that the **product difference** between pairs `(nums[w], nums[x])` and `(nums[y], nums[z])` is **maximized**.

Return _the **maximum** such product difference_.

**Example 1:**

**Input:** nums = \[5,6,2,7,4\]
**Output:** 34
**Explanation:** We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 \* 7) - (2 \* 4) = 34.

**Example 2:**

**Input:** nums = \[4,2,5,9,7,4,8\]
**Output:** 64
**Explanation:** We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 \* 8) - (2 \* 4) = 64.

**Constraints:**

*   `4 <= nums.length <= 104`
*   `1 <= nums[i] <= 104`
Cyclically Rotating a Grid

You are given an `m x n` integer matrix `grid`​​​, where `m` and `n` are both **even** integers, and an integer `k`.

The matrix is composed of several layers, which is shown in the below image, where each color is its own layer:

A cyclic rotation of the matrix is done by cyclically rotating **each layer** in the matrix. To cyclically rotate a layer once, each element in the layer will take the place of the adjacent element in the **counter-clockwise** direction. An example rotation is shown below:

Return _the matrix after applying_ `k` _cyclic rotations to it_.

**Example 1:**

**Input:** grid = \[\[40,10\],\[30,20\]\], k = 1
**Output:** \[\[10,20\],\[40,30\]\]
**Explanation:** The figures above represent the grid at every state.

**Example 2:**

**Input:** grid = \[\[1,2,3,4\],\[5,6,7,8\],\[9,10,11,12\],\[13,14,15,16\]\], k = 2
**Output:** \[\[3,4,8,12\],\[2,11,10,16\],\[1,7,6,15\],\[5,9,13,14\]\]
**Explanation:** The figures above represent the grid at every state.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `2 <= m, n <= 50`
*   Both `m` and `n` are **even** integers.
*   `1 <= grid[i][j] <= 5000`
*   `1 <= k <= 109`
Number of Wonderful Substrings

A **wonderful** string is a string where **at most one** letter appears an **odd** number of times.

*   For example, `"ccjjc "` and `"abab "` are wonderful, but `"ab "` is not.

Given a string `word` that consists of the first ten lowercase English letters (`'a'` through `'j'`), return _the **number of wonderful non-empty substrings** in_ `word`_. If the same substring appears multiple times in_ `word`_, then count **each occurrence** separately._

A **substring** is a contiguous sequence of characters in a string.

**Example 1:**

**Input:** word =  "aba "
**Output:** 4
**Explanation:** The four wonderful substrings are underlined below:
-  "**a**ba " ->  "a "
-  "a**b**a " ->  "b "
-  "ab**a** " ->  "a "
-  "**aba** " ->  "aba "

**Example 2:**

**Input:** word =  "aabb "
**Output:** 9
**Explanation:** The nine wonderful substrings are underlined below:
-  "**a**abb " ->  "a "
-  "**aa**bb " ->  "aa "
-  "**aab**b " ->  "aab "
-  "**aabb** " ->  "aabb "
-  "a**a**bb " ->  "a "
-  "a**abb** " ->  "abb "
-  "aa**b**b " ->  "b "
-  "aa**bb** " ->  "bb "
-  "aab**b** " ->  "b "

**Example 3:**

**Input:** word =  "he "
**Output:** 2
**Explanation:** The two wonderful substrings are underlined below:
-  "**h**e " ->  "h "
-  "h**e** " ->  "e "

**Constraints:**

*   `1 <= word.length <= 105`
*   `word` consists of lowercase English letters from `'a'` to `'j'`.
Count Ways to Build Rooms in an Ant Colony

You are an ant tasked with adding `n` new rooms numbered `0` to `n-1` to your colony. You are given the expansion plan as a **0-indexed** integer array of length `n`, `prevRoom`, where `prevRoom[i]` indicates that you must build room `prevRoom[i]` before building room `i`, and these two rooms must be connected **directly**. Room `0` is already built, so `prevRoom[0] = -1`. The expansion plan is given such that once all the rooms are built, every room will be reachable from room `0`.

You can only build **one room** at a time, and you can travel freely between rooms you have **already built** only if they are **connected**. You can choose to build **any room** as long as its **previous room** is already built.

Return _the **number of different orders** you can build all the rooms in_. Since the answer may be large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** prevRoom = \[-1,0,1\]
**Output:** 1
**Explanation:** There is only one way to build the additional rooms: 0 -> 1 -> 2

**Example 2:**

**Input:** prevRoom = \[-1,0,0,1,2\]
**Output:** 6
**Explanation:**
The 6 ways are:
0 -> 1 -> 3 -> 2 -> 4
0 -> 2 -> 4 -> 1 -> 3
0 -> 1 -> 2 -> 3 -> 4
0 -> 1 -> 2 -> 4 -> 3
0 -> 2 -> 1 -> 3 -> 4
0 -> 2 -> 1 -> 4 -> 3

**Constraints:**

*   `n == prevRoom.length`
*   `2 <= n <= 105`
*   `prevRoom[0] == -1`
*   `0 <= prevRoom[i] < n` for all `1 <= i < n`
*   Every room is reachable from room `0` once all the rooms are built.
Kth Smallest Subarray Sum

Given an integer array `nums` of length `n` and an integer `k`, return _the_ `kth` _**smallest subarray sum**._

A **subarray** is defined as a **non-empty** contiguous sequence of elements in an array. A **subarray sum** is the sum of all elements in the subarray.

**Example 1:**

**Input:** nums = \[2,1,3\], k = 4
**Output:** 3
**Explanation:** The subarrays of \[2,1,3\] are:
- \[2\] with sum 2
- \[1\] with sum 1
- \[3\] with sum 3
- \[2,1\] with sum 3
- \[1,3\] with sum 4
- \[2,1,3\] with sum 6 
Ordering the sums from smallest to largest gives 1, 2, 3, 3, 4, 6. The 4th smallest is 3.

**Example 2:**

**Input:** nums = \[3,3,5,5\], k = 7
**Output:** 10
**Explanation:** The subarrays of \[3,3,5,5\] are:
- \[3\] with sum 3
- \[3\] with sum 3
- \[5\] with sum 5
- \[5\] with sum 5
- \[3,3\] with sum 6
- \[3,5\] with sum 8
- \[5,5\] with sum 10
- \[3,3,5\], with sum 11
- \[3,5,5\] with sum 13
- \[3,3,5,5\] with sum 16
Ordering the sums from smallest to largest gives 3, 3, 5, 5, 6, 8, 10, 11, 13, 16. The 7th smallest is 10.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 2 * 104`
*   `1 <= nums[i] <= 5 * 104`
*   `1 <= k <= n * (n + 1) / 2`
Build Array from Permutation

Given a **zero-based permutation** `nums` (**0-indexed**), build an array `ans` of the **same length** where `ans[i] = nums[nums[i]]` for each `0 <= i < nums.length` and return it.

A **zero-based permutation** `nums` is an array of **distinct** integers from `0` to `nums.length - 1` (**inclusive**).

**Example 1:**

**Input:** nums = \[0,2,1,5,3,4\]
**Output:** \[0,1,2,4,5,3\]
**Explanation:** The array ans is built as follows: 
ans = \[nums\[nums\[0\]\], nums\[nums\[1\]\], nums\[nums\[2\]\], nums\[nums\[3\]\], nums\[nums\[4\]\], nums\[nums\[5\]\]\]
    = \[nums\[0\], nums\[2\], nums\[1\], nums\[5\], nums\[3\], nums\[4\]\]
    = \[0,1,2,4,5,3\]

**Example 2:**

**Input:** nums = \[5,0,1,2,3,4\]
**Output:** \[4,5,0,1,2,3\]
**Explanation:** The array ans is built as follows:
ans = \[nums\[nums\[0\]\], nums\[nums\[1\]\], nums\[nums\[2\]\], nums\[nums\[3\]\], nums\[nums\[4\]\], nums\[nums\[5\]\]\]
    = \[nums\[5\], nums\[0\], nums\[1\], nums\[2\], nums\[3\], nums\[4\]\]
    = \[4,5,0,1,2,3\]

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `0 <= nums[i] < nums.length`
*   The elements in `nums` are **distinct**.

**Follow-up:** Can you solve it without using an extra space (i.e., `O(1)` memory)?
Eliminate Maximum Number of Monsters

You are playing a video game where you are defending your city from a group of `n` monsters. You are given a **0-indexed** integer array `dist` of size `n`, where `dist[i]` is the **initial distance** in kilometers of the `ith` monster from the city.

The monsters walk toward the city at a **constant** speed. The speed of each monster is given to you in an integer array `speed` of size `n`, where `speed[i]` is the speed of the `ith` monster in kilometers per minute.

You have a weapon that, once fully charged, can eliminate a **single** monster. However, the weapon takes **one minute** to charge.The weapon is fully charged at the very start.

You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a **loss**, and the game ends before you can use your weapon.

Return _the **maximum** number of monsters that you can eliminate before you lose, or_ `n` _if you can eliminate all the monsters before they reach the city._

**Example 1:**

**Input:** dist = \[1,3,4\], speed = \[1,1,1\]
**Output:** 3
**Explanation:**
In the beginning, the distances of the monsters are \[1,3,4\]. You eliminate the first monster.
After a minute, the distances of the monsters are \[X,2,3\]. You eliminate the second monster.
After a minute, the distances of the monsters are \[X,X,2\]. You eliminate the thrid monster.
All 3 monsters can be eliminated.

**Example 2:**

**Input:** dist = \[1,1,2,3\], speed = \[1,1,1,1\]
**Output:** 1
**Explanation:**
In the beginning, the distances of the monsters are \[1,1,2,3\]. You eliminate the first monster.
After a minute, the distances of the monsters are \[X,0,1,2\], so you lose.
You can only eliminate 1 monster.

**Example 3:**

**Input:** dist = \[3,2,4\], speed = \[5,3,2\]
**Output:** 1
**Explanation:**
In the beginning, the distances of the monsters are \[3,2,4\]. You eliminate the first monster.
After a minute, the distances of the monsters are \[X,0,2\], so you lose.
You can only eliminate 1 monster.

**Constraints:**

*   `n == dist.length == speed.length`
*   `1 <= n <= 105`
*   `1 <= dist[i], speed[i] <= 105`
Count Good Numbers

A digit string is **good** if the digits **(0-indexed)** at **even** indices are **even** and the digits at **odd** indices are **prime** (`2`, `3`, `5`, or `7`).

*   For example, `"2582 "` is good because the digits (`2` and `8`) at even positions are even and the digits (`5` and `2`) at odd positions are prime. However, `"3245 "` is **not** good because `3` is at an even index but is not even.

Given an integer `n`, return _the **total** number of good digit strings of length_ `n`. Since the answer may be large, **return it modulo** `109 + 7`.

A **digit string** is a string consisting of digits `0` through `9` that may contain leading zeros.

**Example 1:**

**Input:** n = 1
**Output:** 5
**Explanation:** The good numbers of length 1 are  "0 ",  "2 ",  "4 ",  "6 ",  "8 ".

**Example 2:**

**Input:** n = 4
**Output:** 400

**Example 3:**

**Input:** n = 50
**Output:** 564908303

**Constraints:**

*   `1 <= n <= 1015`
Longest Common Subpath

There is a country of `n` cities numbered from `0` to `n - 1`. In this country, there is a road connecting **every pair** of cities.

There are `m` friends numbered from `0` to `m - 1` who are traveling through the country. Each one of them will take a path consisting of some cities. Each path is represented by an integer array that contains the visited cities in order. The path may contain a city **more than once**, but the same city will not be listed consecutively.

Given an integer `n` and a 2D integer array `paths` where `paths[i]` is an integer array representing the path of the `ith` friend, return _the length of the **longest common subpath** that is shared by **every** friend's path, or_ `0` _if there is no common subpath at all_.

A **subpath** of a path is a contiguous sequence of cities within that path.

**Example 1:**

**Input:** n = 5, paths = \[\[0,1,2,3,4\],
                       \[2,3,4\],
                       \[4,0,1,2,3\]\]
**Output:** 2
**Explanation:** The longest common subpath is \[2,3\].

**Example 2:**

**Input:** n = 3, paths = \[\[0\],\[1\],\[2\]\]
**Output:** 0
**Explanation:** There is no common subpath shared by the three paths.

**Example 3:**

**Input:** n = 5, paths = \[\[0,1,2,3,4\],
                       \[4,3,2,1,0\]\]
**Output:** 1
**Explanation:** The possible longest common subpaths are \[0\], \[1\], \[2\], \[3\], and \[4\]. All have a length of 1.

**Constraints:**

*   `1 <= n <= 105`
*   `m == paths.length`
*   `2 <= m <= 105`
*   `sum(paths[i].length) <= 105`
*   `0 <= paths[i][j] < n`
*   The same city is not listed multiple times consecutively in `paths[i]`.
Erect the Fence II

You are given a 2D integer array `trees` where `trees[i] = [xi, yi]` represents the location of the `ith` tree in the garden.

You are asked to fence the entire garden using the minimum length of rope possible. The garden is well-fenced only if **all the trees are enclosed** and the rope used **forms a perfect circle**. A tree is considered enclosed if it is inside or on the border of the circle.

More formally, you must form a circle using the rope with a center `(x, y)` and radius `r` where all trees lie inside or on the circle and `r` is **minimum**.

Return _the center and radius of the circle as a length 3 array_ `[x, y, r]`_._ Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input:** trees = \[\[1,1\],\[2,2\],\[2,0\],\[2,4\],\[3,3\],\[4,2\]\]
**Output:** \[2.00000,2.00000,2.00000\]
**Explanation:** The fence will have center = (2, 2) and radius = 2

**Example 2:**

**Input:** trees = \[\[1,2\],\[2,2\],\[4,2\]\]
**Output:** \[2.50000,2.00000,1.50000\]
**Explanation:** The fence will have center = (2.5, 2) and radius = 1.5

**Constraints:**

*   `1 <= trees.length <= 3000`
*   `trees[i].length == 2`
*   `0 <= xi, yi <= 3000`
Count Square Sum Triples

A **square triple** `(a,b,c)` is a triple where `a`, `b`, and `c` are **integers** and `a2 + b2 = c2`.

Given an integer `n`, return _the number of **square triples** such that_ `1 <= a, b, c <= n`.

**Example 1:**

**Input:** n = 5
**Output:** 2
**Explanation**: The square triples are (3,4,5) and (4,3,5).

**Example 2:**

**Input:** n = 10
**Output:** 4
**Explanation**: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).

**Constraints:**

*   `1 <= n <= 250`
Nearest Exit from Entrance in Maze

You are given an `m x n` matrix `maze` (**0-indexed**) with empty cells (represented as `'.'`) and walls (represented as `'+'`). You are also given the `entrance` of the maze, where `entrance = [entrancerow, entrancecol]` denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell **up**, **down**, **left**, or **right**. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the **nearest exit** from the `entrance`. An **exit** is defined as an **empty cell** that is at the **border** of the `maze`. The `entrance` **does not count** as an exit.

Return _the **number of steps** in the shortest path from the_ `entrance` _to the nearest exit, or_ `-1` _if no such path exists_.

**Example 1:**

**Input:** maze = \[\[ "+ ", "+ ", ". ", "+ "\],\[ ". ", ". ", ". ", "+ "\],\[ "+ ", "+ ", "+ ", ". "\]\], entrance = \[1,2\]
**Output:** 1
**Explanation:** There are 3 exits in this maze at \[1,0\], \[0,2\], and \[2,3\].
Initially, you are at the entrance cell \[1,2\].
- You can reach \[1,0\] by moving 2 steps left.
- You can reach \[0,2\] by moving 1 step up.
It is impossible to reach \[2,3\] from the entrance.
Thus, the nearest exit is \[0,2\], which is 1 step away.

**Example 2:**

**Input:** maze = \[\[ "+ ", "+ ", "+ "\],\[ ". ", ". ", ". "\],\[ "+ ", "+ ", "+ "\]\], entrance = \[1,0\]
**Output:** 2
**Explanation:** There is 1 exit in this maze at \[1,2\].
\[1,0\] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell \[1,0\].
- You can reach \[1,2\] by moving 2 steps right.
Thus, the nearest exit is \[1,2\], which is 2 steps away.

**Example 3:**

**Input:** maze = \[\[ ". ", "+ "\]\], entrance = \[0,0\]
**Output:** -1
**Explanation:** There are no exits in this maze.

**Constraints:**

*   `maze.length == m`
*   `maze[i].length == n`
*   `1 <= m, n <= 100`
*   `maze[i][j]` is either `'.'` or `'+'`.
*   `entrance.length == 2`
*   `0 <= entrancerow < m`
*   `0 <= entrancecol < n`
*   `entrance` will always be an empty cell.
Sum Game

Alice and Bob take turns playing a game, with **Alice** **starting first**.

You are given a string `num` of **even length** consisting of digits and `'?'` characters. On each turn, a player will do the following if there is still at least one `'?'` in `num`:

1.  Choose an index `i` where `num[i] == '?'`.
2.  Replace `num[i]` with any digit between `'0'` and `'9'`.

The game ends when there are no more `'?'` characters in `num`.

For Bob to win, the sum of the digits in the first half of `num` must be **equal** to the sum of the digits in the second half. For Alice to win, the sums must **not be equal**.

*   For example, if the game ended with `num = "243801 "`, then Bob wins because `2+4+3 = 8+0+1`. If the game ended with `num = "243803 "`, then Alice wins because `2+4+3 != 8+0+3`.

Assuming Alice and Bob play **optimally**, return `true` _if Alice will win and_ `false` _if Bob will win_.

**Example 1:**

**Input:** num =  "5023 "
**Output:** false
**Explanation:** There are no moves to be made.
The sum of the first half is equal to the sum of the second half: 5 + 0 = 2 + 3.

**Example 2:**

**Input:** num =  "25?? "
**Output:** true
**Explanation:** Alice can replace one of the '?'s with '9' and it will be impossible for Bob to make the sums equal.

**Example 3:**

**Input:** num =  "?3295??? "
**Output:** false
**Explanation:** It can be proven that Bob will always win. One possible outcome is:
- Alice replaces the first '?' with '9'. num =  "93295??? ".
- Bob replaces one of the '?' in the right half with '9'. num =  "932959?? ".
- Alice replaces one of the '?' in the right half with '2'. num =  "9329592? ".
- Bob replaces the last '?' in the right half with '7'. num =  "93295927 ".
Bob wins because 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7.

**Constraints:**

*   `2 <= num.length <= 105`
*   `num.length` is **even**.
*   `num` consists of only digits and `'?'`.
Minimum Cost to Reach Destination in Time

There is a country of `n` cities numbered from `0` to `n - 1` where **all the cities are connected** by bi-directional roads. The roads are represented as a 2D integer array `edges` where `edges[i] = [xi, yi, timei]` denotes a road between cities `xi` and `yi` that takes `timei` minutes to travel. There may be multiple roads of differing travel times connecting the same two cities, but no road connects a city to itself.

Each time you pass through a city, you must pay a passing fee. This is represented as a **0-indexed** integer array `passingFees` of length `n` where `passingFees[j]` is the amount of dollars you must pay when you pass through city `j`.

In the beginning, you are at city `0` and want to reach city `n - 1` in `maxTime` **minutes or less**. The **cost** of your journey is the **summation of passing fees** for each city that you passed through at some moment of your journey (**including** the source and destination cities).

Given `maxTime`, `edges`, and `passingFees`, return _the **minimum cost** to complete your journey, or_ `-1` _if you cannot complete it within_ `maxTime` _minutes_.

**Example 1:**

**Input:** maxTime = 30, edges = \[\[0,1,10\],\[1,2,10\],\[2,5,10\],\[0,3,1\],\[3,4,10\],\[4,5,15\]\], passingFees = \[5,1,2,20,20,3\]
**Output:** 11
**Explanation:** The path to take is 0 -> 1 -> 2 -> 5, which takes 30 minutes and has $11 worth of passing fees.

**Example 2:**

**Input:** maxTime = 29, edges = \[\[0,1,10\],\[1,2,10\],\[2,5,10\],\[0,3,1\],\[3,4,10\],\[4,5,15\]\], passingFees = \[5,1,2,20,20,3\]
**Output:** 48
**Explanation:** The path to take is 0 -> 3 -> 4 -> 5, which takes 26 minutes and has $48 worth of passing fees.
You cannot take path 0 -> 1 -> 2 -> 5 since it would take too long.

**Example 3:**

**Input:** maxTime = 25, edges = \[\[0,1,10\],\[1,2,10\],\[2,5,10\],\[0,3,1\],\[3,4,10\],\[4,5,15\]\], passingFees = \[5,1,2,20,20,3\]
**Output:** -1
**Explanation:** There is no way to reach city 5 from city 0 within 25 minutes.

**Constraints:**

*   `1 <= maxTime <= 1000`
*   `n == passingFees.length`
*   `2 <= n <= 1000`
*   `n - 1 <= edges.length <= 1000`
*   `0 <= xi, yi <= n - 1`
*   `1 <= timei <= 1000`
*   `1 <= passingFees[j] <= 1000`
*   The graph may contain multiple edges between two nodes.
*   The graph does not contain self loops.