有 $n$ 个车站以及它们之间的 $m$ 条有向道路。

有一天，Chiaki 要从第 $s$ 个车站前往第 $t$ 个车站，然后再回到第 $s$ 个车站。在此过程中，他需要为他经过的车站购买车票。第 $i$ 个车站的票价为 $p_i$。如果 Chiaki 购买了第 $i$ 个车站的车票，他就可以无限次经过该车站。求购买车票所需的最低总价格。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 200$)，表示测试数据的组数。对于每组测试数据：

第一行包含四个整数 $n, m, s$ 和 $t$ ($1 \le n \le 200, 0 \le m \le n \times (n - 1), 1 \le s, t \le n$)。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 100$)。 接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，表示一条从第 $a_i$ 个车站到第 $b_i$ 个车站的道路 ($1 \le a_i, b_i \le n$)。

所有 $n$ 的总和不超过 200。

输出格式

对于每组测试数据，输出一个整数，表示答案。

样例

样例输入 1

3
4 5 1 4
1 1 1 1
1 2
2 3
3 1
4 2
3 4
4 4 1 2
1 1 1 1
1 2
2 3
3 4
4 1
4 8 1 3
1 100 1 1
1 2
2 1
2 3
3 2
1 4
4 1
3 4
4 3

样例输出 1

4
4
3