可怜的兔子，可怜的爱丽丝。

白兔正在通过他的神圣旅行日志帮助爱丽丝寻找一条回家的捷径。问题在于他那古怪的怀表（它显示的时刻是从 0 到 12），以及他记录时间的方式：如果一段旅程花费了 14 小时（实际时间），看到指针停在数字 1 上方，他就会认为这段旅程花费了一个小时。

既然白兔说的是真话，你能利用白兔的旅行日志帮助爱丽丝找到回家的最短路径吗？

任务

你的任务是找到爱丽丝从她当前位置到达兔子洞所需的最短实际时间。对于每一次旅行，白兔都记录了旅行时间、访问过的地点数量（不一定不同）以及访问地点的序列。该序列定义了这次旅行，因为仙境中任意两个地点之间最多只有一条直接路径，且往返所需时间相同。

输入格式

第一行包含四个整数 $N, A, R$ 和 $T$，其中：$N$ 是不同地点的数量；$A$ 标识爱丽丝所在的位置；$R$ 对应兔子洞的位置；$T$ 是白兔日志中记录的旅行次数。所有地点均用从 $1$ 到 $N$ 的数字标识。接下来的 $T$ 行，每行描述一次记录的旅行，格式为 $d \ p \ a_1 \ a_2 \dots a_p$，其中 $d$ 是旅行持续时间（根据白兔的怀表），$p$ 是地点数量，$a_1 \ a_2 \dots a_p$ 是访问地点的序列。

数据范围

• $2 \le N \le 200$ 地点数量
• $1 \le T \le 500$ 日志中的旅行次数
• $2 \le p \le 800$ 一次旅行中访问的地点数量（可能重复）
• $1 \le d_{ij} \le 12$ 地点 $a_i$ 和 $a_j$ 之间直接路径的实际时间（如果存在）
• 最多有 200 条直接路径

输出格式

一个整数，表示爱丽丝回家所需的最短（实际）时间。

样例

样例输入 1

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

样例输出 1

9

样例输入 2

5 5 1 9
0 3 1 2 3
1 4 1 4 2 3
6 4 3 4 1 3
11 5 1 3 4 2 1
4 4 1 2 4 1
6 6 1 2 3 1 4 3
7 4 2 3 4 1
11 3 4 3 5
12 5 5 2 4 2 5

样例输出 2

6