In Clash Royale 2, instead of there being 1 layer of bridges, there are now $$$n$$$ layers of bridges. While playing the game, your King Tower is located at the origin, $$$(0,0)$$$, the $$$i^\text{th}$$$ layer of bridges is located at $$$y=l_i$$$, and the enemy King Tower is located on the other side of the playing field at $$$(0,m+1)$$$. There are also $$$k$$$ bridges, with the $$$j^\text{th}$$$ bridge located at a single point, $$$(x_j, l_{y_j})$$$, each of which has a debuff value, $$$d_j$$$.
Bandit wants to cross from your King Tower to the enemy King Tower by dashing as quickly as possible. Initially, Bandit has a debuff of $$$1$$$. When dashing, Bandit can only do $$$1$$$ of the following actions:
If the Bandit dashes to bridge $$$j$$$, Bandit's debuff now becomes $$$d_j$$$. If Bandit dashes from $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$, then it takes $$$D\cdot \left|x_1-x_2\right|\cdot \left|y_1-y_2\right|$$$ seconds, where $$$D$$$ is Bandit's debuff before dashing. Crossing a bridge takes $$$0$$$ seconds.
Given the layout of the playing field, help Bandit find the minimum time it takes to dash from your King Tower to the enemy King Tower. It is guaranteed that every bridge is on a layer and that every layer has at least $$$1$$$ bridge. It is also guaranteed that no $$$2$$$ bridges are at the exact same coordinates.
The first line of input contains $$$n$$$, $$$k$$$, and $$$m$$$ ($$$1\le n\le k,m\le 10^6$$$) — the number of layers of bridges, the number of bridges, and the length of the playing field, respectively.
The next line of input contains $$$n$$$ numbers, $$$l_1, l_2, \ldots ,l_n$$$ ($$$1\le l_1 \lt l_2 \lt \cdots \lt l_n \le m$$$) — the $$$y$$$-levels of the bridge layers.
The $$$j^\text{th}$$$ of the next $$$k$$$ lines contains $$$3$$$ space-separated integers, $$$x_j$$$, $$$y_j$$$, and $$$d_j$$$ ($$$-10^6\le x\le10^6, 1\le y_j\le n, 1\le d_j\le10^6$$$) — the $$$x$$$-coordinate of the $$$j^\text{th}$$$ bridge, the index of the bridge layer it belongs to, and the debuff of the bridge, respectively. It is guaranteed that every bridge is on a layer and that every layer has at least $$$1$$$ bridge. It is also guaranteed that no $$$2$$$ bridges are at the exact same coordinates.
Output a single integer, the minimum time, in seconds, it takes for Bandit to dash from your King Tower to the enemy King Tower.
3 5 51 2 5-3 1 3-1 3 20 2 101 3 42 2 1
25
Bandit starts at $$$(0,0)$$$, your King Tower, with a debuff of $$$1$$$.
Bandit can then dash from $$$(0,0)$$$ to bridge $$$1$$$, located at $$$(-3,1)$$$. This takes $$$1\cdot \left|0-(-3)\right|\cdot\left|0-1\right| = 3$$$ seconds to complete. This also updates Bandit's debuff to $$$3$$$.
Bandit can then dash from $$$(-3,1)$$$ to bridge $$$5$$$, located at $$$(2,2)$$$. This takes $$$3\cdot\left|-3-2\right|\cdot\left|1-2\right| = 15$$$ seconds to complete. This also updates Bandit's debuff to $$$1$$$.
Bandit can then dash from $$$(2,2)$$$ to bridge $$$4$$$, located at $$$(1,5)$$$. This takes $$$1\cdot\left|2-1\right|\cdot\left|2-5\right| = 3$$$ seconds to complete. This also updates Bandit's debuff to $$$4$$$.
Bandit can then dash from $$$(1,5)$$$ to the enemy King Tower, located at $$$(0,6)$$$. This takes $$$4\cdot\left|2-1\right|\cdot\left|5-6\right|=4$$$ seconds to complete.
This entire journey takes $$$3+15+3+4=25$$$ seconds to complete. It can be proven that this is the shortest time possible.
