Keyboards in Concert

Source: Kattis

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. Có $n$ bàn phím điện tử. Mỗi bàn phím chỉ chơi được một tập nốt nhất định. Một bản nhạc gồm $m$ nốt theo thứ tự. Hãy chơi toàn bộ bản nhạc với số lần đổi bàn phím ít nhất.

Input

Dòng đầu chứa $n,m$. Mỗi trong $n$ dòng tiếp theo bắt đầu bằng $k_i$ rồi liệt kê các nốt bàn phím $i$ chơi được. Dòng cuối chứa $m$ nốt của bản nhạc.

Output

In số lần đổi bàn phím nhỏ nhất.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

3 9
2 1 2
2 2 3
1 3
1 2 1 2 3 3 2 3 1

Output

2

Explanation

The output follows directly from the rules above.