You are given an array start = [startX, startY] representing your initial position and an array target = [targetX, targetY] representing your destination on a $2$D plane.

You can travel between any two points $(x_1, y_1)$ and $(x_2, y_2)$ with a cost equal to the Manhattan distance $|x_2 - x_1| + |y_2 - y_1|$.

Additionally, you are provided with a $2$D array specialRoads where specialRoads[i] = [x1_i, y1_i, x2_i, y2_i, cost_i] represents a directed special road that allows you to travel from $(x1_i, y1_i)$ to $(x2_i, y2_i)$ for a cost of cost_i. Each special road can be used any number of times.

Return the minimum cost required to travel from start to target.

Constraints:

• start.length $= {target.length} = 2$

• $1 \leq$ startX $\leq$ targetX $\leq 10^5$

• $1 \leq$ startY $\leq$ targetY $\leq 10^5$

• $1 \leq$ specialRoads.length $\leq 200$

• specialRoads[i].length $= 5$

• startX $\leq x1_i, x2_i \leq$ targetX

• startY $\leq y1_i, y2_i \leq$ targetY

• $1 \leq cost_i \leq 10^5$

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.