题目描述

小理所在的城市一共有 $m$ 条地铁线，分别标号为 $1$ 号线，$2$ 号线，……，$m$ 号线。

整个城市一共有 $n$ 个车站，编号为 $1 \sim n$ 。其中坐 $i$ 号线需要花费 $a_i$ 的价格，每坐一站就需要多花费 $b_i$ 的价格。$i$ 号线有 $c_i$ 个车站，而且这 $c_i$ 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。

现在小理想从第 $s$ 个车站坐地铁到第 $t$ 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 $-1$ 。（地铁是双向的，所以 $s$ 可能大于 $t$）。

输入格式

输入共 $m+1$ 行。

第一行输入四个正整数 $n,m,s,t$，分别表示车站个数，地铁线数，起点站和终点站。

第二行到第 $m + 1$ 行，每行前三个数为 $a_i,b_i,c_i$，分别表示坐 $i$ 号线的价格，$i$ 号线每坐一站多花的价格，$i$ 号线车站个数。接下来 $c_i$ 个数，表示 $i$ 号线的每一个车站的编号，单调递增。

输出格式

共一行，一个数表示最小花费，若不能到达输出 $-1$ 。

样例输入输出

样例输入

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

样例输出

7

数据范围

对于 $100%$ 的数据，保证 $1 \le n \le 10^{3},1 \le m \le 500,1 \le s,t \le n,1 \le a_i,b_i \le 100,1 \le c_i \le n,\sum^{m}_{i=1}c_i \le 10^{5}$。