E. Charging Adapters
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ vertices, numbered $$$1,2,\ldots,n$$$. The coordinate of vertex $$$i$$$ is $$$x_i$$$, where $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$. Each vertex supports a nonempty subset of $$$k$$$ types. A state is a pair $$$(i,c)$$$ such that vertex $$$i$$$ supports type $$$c$$$.

From a state $$$(i,c)$$$, the following transitions are allowed:

  • Choose one direction on the coordinate line and move to the vertex $$$j$$$ nearest to vertex $$$i$$$ in that direction that supports type $$$c$$$. This transition leads to $$$(j,c)$$$ and costs $$$|x_i-x_j|$$$. If no such vertex exists, the transition is unavailable.
  • Change the type from $$$c$$$ to any type $$$d$$$ supported by vertex $$$i$$$. This transition leads to $$$(i,d)$$$ and costs $$$w_{i,d}$$$. Keeping type $$$c$$$ costs nothing.

Initially, you are at vertex $$$s$$$ without any type. You may change to any type $$$c$$$ supported by vertex $$$s$$$ at a cost of $$$w_{s,c}$$$. Find the minimum total cost of reaching vertex $$$t$$$. You may reach vertex $$$t$$$ with any type it supports.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains four integers $$$n$$$, $$$k$$$, $$$s$$$, and $$$t$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le k \le 200\,000$$$, $$$1 \le s,t \le n$$$, $$$s \ne t$$$).

The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$0 \le x_1 \lt x_2 \lt \ldots \lt x_n \le 10^9$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains an integer $$$m_i$$$ ($$$1 \le m_i \le k$$$), followed by $$$m_i$$$ pairs of integers $$$c_{i,j}$$$ and $$$w_{i,j}$$$ ($$$1 \le c_{i,j} \le k$$$, $$$0 \le w_{i,j} \le 10^9$$$). Each pair means that the corresponding vertex $$$i$$$ supports type $$$c_{i,j}$$$ and that changing to this type there costs $$$w_{i,j}$$$. All types listed for one vertex are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200\,000$$$, the sum of $$$k$$$ over all test cases does not exceed $$$200\,000$$$, and the sum of $$$m_i$$$ over all vertices and test cases does not exceed $$$200\,000$$$.

Output

For each test case, output the minimum total cost of reaching vertex $$$t$$$ from vertex $$$s$$$. If it is impossible, print a single integer $$$-1$$$.

Example
Input
2
5 3 1 5
0 4 7 13 20
2 1 0 2 3
2 2 1 3 8
2 1 2 3 1
1 2 4
2 1 5 2 2
3 2 1 3
0 5 9
1 1 0
1 2 1
1 2 0
Output
20
-1
Note

In the first test case, changing to type $$$1$$$ at vertex $$$1$$$ costs $$$0$$$. From vertex $$$1$$$, move right to vertex $$$3$$$, the nearest vertex in that direction that supports type $$$1$$$. From vertex $$$3$$$, move right to vertex $$$5$$$. The transition costs are $$$0$$$, $$$7$$$, and $$$13$$$, respectively, for a total of $$$20$$$.

In the second test case, no type supported by vertex $$$1$$$ is also supported by another vertex, so no movement transition from vertex $$$1$$$ is available.