問題文

データセンターから出ると、外はもう高く太陽が昇っていた。

とにかく眠かった。午前2時頃から始まったニコニコ一斉メンテナンスは、予定通り午前10時頃に終了した。超過勤務ではなかったとはいえ、僕は生活リズムをずらすのがあまり得意ではないので、メンテナンス開始前にあまり睡眠を取れなかったのだ。一刻も早く家に帰って布団にダイブしたい・・・が、その前に電車を寝過ごすことなく無事に帰れるのかという不安があった。

N 個の駅と、 M 路線の電車からなる電車網がある。各路線は上り下り両方向に利用でき、ある路線が同じ駅に2回以上停車することはない。

僕はこの電車網を使って、駅 src から駅 dst へ移動したい。 しかし電車に乗り、その路線の停車駅間を移動しているときはいつでも眠り込んでしまう可能性がある。 眠ってしまった場合、本来降りるはずだった駅を通り過ぎて、その進行方向の終点の駅まで乗り続けてしまう。 終点の駅で目を覚ました後はすっきりするので、それ以降は電車を乗り過ごすことはなく、好きな経路で目的の駅まで移動できるだろう。

厄介なことに、僕は仕事中にエナジードリンクを飲んでしまっていて、まだ体からカフェインが抜けていない。つまり、移動中のどのタイミングに眠り込んでしまうかは全く予想できないのだ。

うまく移動経路を選んで、最も悪いタイミングで眠り込んだときの最終的な移動時間が最小になるようにしたい。そのような場合の移動時間はいくらだろうか？

入力

入力は以下の形式で与えられる。

N M src dst
L_{0}
s_{0,0} s_{0,1} ... s_{0,L_{0}-1}
w_{0,0} w_{0,1} ... w_{0,L_{0}-2}
L_{1}
s_{1,0} s_{1,1} ... s_{1,L_{1}-1}
w_{1,0} w_{1,1} ... w_{1,L_{1}-2}
:

最初の行に N, M, src, dst (0 \leq src, dst < N) が与えられ、続く行に路線の情報が与えられる。

各路線の情報は3行で与えられる。 最初の行にはその路線に含まれる駅の数 L_{i} が与えられる。 2行目にはその路線が停車する駅が順に与えられる。 3行目には駅間の移動所要時間を表す L_{i} - 1 個の整数が与えられ、その j 番目の数はその路線の j 番目の駅と j+1 番目の駅の間の所要時間を示す（どちらの駅からどちらの駅に向かう場合でも所要時間は等しい）。路線の j 番目の駅から j+1 番目の駅への移動中に寝過ごした場合は L_{i} - 1 番目の駅まで移動することになり、路線の j+1 番目の駅から j 番目の駅への移動中に寝過ごした場合は 0 番目の駅まで移動することになる。同じ駅間を直接繋ぐ路線は複数あるかもしれないし、そのような場合には路線によって所要時間が異なるかもしれないことに注意せよ。

入力は以下の制約を満たす。

• 2 \leq N \leq 25,252
• 2 \leq L_{i} (0 \leq i < M)
• L_{0} + L_{1} + ... + L_{M-1} \leq 252,525
• 1 \leq w_{i,j} \leq 2,525
• src \neq dst
• どの路線も同じ駅に2回以上停まることはない。すなわち、j \neq k ならば s_{i,j} \neq s_{i,k}
• src と dst 間の経路は1つ以上存在する

配点

部分点が設定されており、50 点分のデータセットは追加で以下の制約を満たす。

• N \leq 252
• L_{0} + L_{1} + ... + L_{M-1} \leq 525
• w_{i,j} \leq 25

出力

問題文中で問われる移動時間を1行に出力せよ。出力の最後に改行を忘れないこと。

入力例1

5 2 0 3
3
0 1 2
1 2
3
1 3 4
1 1

出力例1

6

駅 0 から 1 に移動するときに寝過ごしてしまう可能性があるため、最適な経路は 0 - 1 - 2 - 1 - 3 となり、そのコストは 6 である。

入力例2

5 2 0 3
3
0 1 2
1 1
3
1 3 4
1 3

出力例2

8

入力例1と同形の電車網だが、駅間の移動時間だけが異なる。これにより、駅 0 - 1 間で寝過ごすよりも 1 - 3 間で寝過ごす方が所要時間が長くなってしまう。

移動中のどのタイミングで眠り込んでしまうかはコントロールできないことに注意せよ。 駅 0 - 1 - 2 間をどのように移動したとしても、ここで寝過ごすような経路を考えることはできない。駅 3 に辿り着くためには必ず駅 1 - 3 間を移動しなければならず、ここで寝過ごした方が悪い結果が得られてしまうためである。

入力例3

4 2 0 1
3
0 1 2
1 3
3
0 3 1
1 1

出力例3

2

最初の路線を使うと、寝過ごした場合に遠くまで運ばれてしまう。2つ目の路線は終着駅が目的地なので、どこで寝過ごそうとも時間 2 で目的地に辿り着くことが保証される。